有重复数字的二分查找（找到最靠前的那一个）

1.暴力遍历，通过简单的遍历就可以实现，时间复杂度O(n),空间复杂度O(1)
import java.util.;
public class Solution {
public int search (int[] nums, int target) {
// write code here
int i=0;
for(;i<nums.length;i++){
if(nums[i]==target)
break;
}
if(i!=nums.length)
return i;
return -1;
}
}
2.二分查找，时间复杂度O(logn),空间复杂度O(1)
（1）自己的思想，有点笨，找到以后就记录结果，并用了一个标记位表示可以找到
import java.util.;
public class Solution {
public int search (int[] nums, int target) {
// write code here
int low=0,high=nums.length-1;
int res=0;
boolean flag=false;
while(low<=high){
int mid=(low+high)/2;
if(nums[mid]==target){
high=mid-1;
res=mid;
flag=true;
continue;
}
if(nums[mid]>target)
{
high=mid-1;
}
if(nums[mid]<target)
low=mid+1;
}
if(flag)
return res;
return -1;
}
}
（2）看了别人的思路
1.逐渐向左靠近，就是把判断条件变成了low<high,相等时就会跳出，找到值就会让左边等于中值，这样就不会把找到的值忽略。
import java.util.;
public class Solution {
public int search (int[] nums, int target) {
// write code here
if(nums.length==0)
return -1;
int low=0,high=nums.length-1;
while(low<high){
int mid=(low+high)/2;
if(nums[mid]<target){
low=mid+1;
}
else{
high=mid;
}
}
if(nums[low]==target)
return low;
return -1;
}
}
2.找到之后继续向左查找，因为找到之后如果前面有的话，一定是相邻的
while(low<=high){
int mid=(low+high)/2;
if(nums[mid]<target){
low=mid+1;
}else if(nums[mid]>target){
high=mid-1;
}else{
while(mid!=0&&nums[mid]==nums[mid-1])
mid--;
return mid;
}
}
3.递归进行二分查找，时间，空间复杂度都是O(logn),需要借用递归栈，依旧是逐渐向左靠近思路
import java.util.;
public class Solution {
public int search (int[] nums, int target) {
// write code here
if(nums.length==0)
return -1;
//递归
return look(nums,target,0,nums.length-1);
}
private int look(int nums[],int target,int left,int right){
if(left>right)
return -1;
if(nums[left]==target)
return left;
int mid=(left+right)/2;
if(nums[mid]<target){
return look(nums,target,mid+1,right);
}else if(nums[mid]>target){
return look(nums,target,left,mid-1);
}else{
return look(nums,target,left,mid);
}
}
}