二分查找

参考博客

第二次刷Leetcode_034题目时，涉及到二分查找左右边界时，又出现了算法理解不清楚的问题。发现第一次也并没有去总结，这里总结下。

二分查找的精髓就是对于细节的把控，搜索空间的定义、左右指针的变换形式，左右指针在左右边界中分别代表的含义等等。都需要细致的理解才可以。

常见的二分查找一个应用场景我们可以分为三种：1.查找一个数 2.查找左边界 3.查找右边界。

二分查找基本框架

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = (right + left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

上面的代码框架就是我们在一开始接触二分查找时所采用的框架形式。

寻找一个数

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) { // 注意
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
        }
    return -1;
}

以上时寻找一个数时采用的代码，其有几个常见的疑问点：

左右指针的初始值： 通常左指针初始化均为0，而右指针经常会看到初始化为$right = len(nums)$ 或者 $right = len(nums) - 1$.这两种写法，我们该如何理解呢？队之后左右指针的更新分别又存在什么样子的影响呢？

答： 左右指针其实就是middle可能遍历的位置范围，我们可以将左右指针看作middle的搜索范围。那么根据初始化右指针的情况不同可以