二分查找思路1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public int Search(int[] nums,int target){
	int left=0;
    int right=nums.length-1;
    while(left<=right){
        int mid=left+(right-left)/2;
        if(nums[mid]==target){
            return nums[mid];
        }
        else if(nums[mid]>target){
            right=mid-1；
        }
        else{
            left=mid+1;
        }
    }
    return -1;
}

二分查找的思路2

• 排除法：考虑中间元素nums[mid] 在什么情况下不是目标元素
• 思路：将待搜索区间分为2个部分，一部分一定不存在目标元素，另一部分可能存在目标元素

写二分查找的一般步骤：

• 将循环条件设置为while(left<right)
• 写if和else语句的时候，思考nums[i]满足什么性质时，nums[mid]不是目标元素，接着判断mid的左边有没有可能存在目标元素，mid的右边有没有可能存在目标元素。
• 根据“边界收缩行为”修改中间数的行为
  • int mid = left +(right - left)/2
  • “/” 是整数除法，默认的取整行为是向下取整，这会带来一个问题：int mid = left +(right - left)/2 永远取不到右边界right，对应的是mid被分到了左边区间。在面对left=mid和right=mid-1这种边界收缩时，就有可能产生死循环。
• 退出循环后，看是否需要对nums[left]是否是目标元素再做一次检查。

参考

链接

链接