704. 二分查找

题目链接
代码随想录

分析

二分查找的使用有前提条件

• 有序数组
• 无重复元素
  二分法经常写乱，主要是因为对搜索区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在 while 寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。
  推荐的写法是左闭右闭区间写法，即 [left, right]，此时会有如下两种结果
• while (left <= right) 要使用 <= ，因为 left == right 是有意义的，所以使用 <=，这个其实很容易理解，假设现在有一个数组 {3,5,7}，我们查找 7，我们用二分查找，首先会找到 5，然后 5 小于目标，我们会让 left 的索引更新到 2，然后查找其值，也就是 num[2]，此时 left==right，这个时候，如果我们设置 while 的循环条件是 (left<right)，就不会检查 num[2]，也就找不到目标值了，所以，允许 left==right，就是为了检查 [left,right] 区间只有一个元素的场景，而这时有可能存在的。所以二分查找的 while 循环条件，必须是 left <= right。
• if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个 nums[middle] 一定不是 target，那么接下来要查找的左区间结束下标位置就是 middle - 1
  还有一点需要提醒的是，我们在写数组的题目的时候，往往会觉得，需要分情况判断 left 或者 right 下标的奇偶性和除以 2 以后的奇偶性上，其实是完全没有必要的，我们求 mid 这个中间下标，并不是要真的精确地求出中间下标，而只是想缩小 left 和 right 这个区间的范围，多一个少一个元素其实并不重要。

还有一点需要注意就是求 mid 的时候，不要写成这样 int mid = (end + start) / 2; 有可能会溢出，举个例子

public class Test {  
    static void main() {  
        System.out.println((Integer.MAX_VALUE+Integer.MAX_VALUE)/2);  
    }  
}

输出

-1

所以我们质能写成这样
int mid = start + (end - start) / 2;

解题

public static int search(int[] nums, int target) {  
    int start = 0, end = nums.length - 1;  
    while (start <= end) {  
        // 其实这里并不需要精确取 start 和 end 的中间，取个大概即可，只要能大约缩减一般的搜索空间即可  
        // int mid = (end + start) / 2; 有可能会溢出  
        int mid = start + (end - start) / 2;  
        if (nums[mid] == target) {  
            return mid;  
        } else if (nums[mid] < target) {  
            start = mid + 1;  
        } else {  
            end = mid - 1;  
        }  
    }  
    return -1;  
}

二分法为什么快？

二分法快就快在，经过一次循环就可以把搜索范围缩小一半，所有的精髓，都在 right = middle - 1; 和 left = middle + 1; 上
二分查找的本质，就是有序数列的一种快速遍历方式
二分法是查找有序数组最快的方式。
有序数组，且无重复元素，且要求使用 $log(n)$ 的时间复杂度，基本上可以认为就是要求你用二分法查找。
推导过程请看 复杂度#二分查找

类似题

35. 搜索插入位置
34. 在排序数组中查找元素的第一个和最后一个位置
69. x 的平方根
367. 有效的完全平方数