手写二分查找，看完这篇你再也不会出错了

我们首先来看一个标准二分查找的写法：

    public int BinarySearch(int[] nums, int target) {
        // write your code here
        if (nums == null) return -1;
        int left = 0;
        int right = nums.length;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return -1;
        // return left; 当未找到时，left的值为target应当插入的下标位置
    }

对于标准的二分查找，你只需要记住以下几点，就可以写得又快又好：

• 左闭右开区间。我们要始终保持区间的左闭右开，主要体现在：
  • left和right的初值
  • while循环条件是left < right，因为是左闭右开，当left == right时，区间长度为0，就需要结束搜索
  • left和right的更新
• 出循环后left的最终位置：结束while循环说明left == right且未找到目标值，此时left的位置为目标值应当应当插入的位置。
• mid的计算：为避免溢出，先减后加计算mid，int mid = left + (right - left) / 2;
• 函数入口处判断数组是否为null：用来提升程序健壮性

对于包含重复值的排序数组，我们可能会想要找到目标值首次出现的位置或最后出现的位置。

我们先看如何找目标值首次出现的位置：

    public int lowerBound(int[] nums, int target) {
        // write your code here
        if (nums == null) return -1;
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (target <= nums[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        if (left < nums.length && nums[left] == target) return left;
        
        return -1;
    }

和标准二分写法不同的是，我们不再对nums[mid] == target进行判断，而是把相等判断融入到if-else中去，以达到一个收缩区间的效果。例如，我们找目标值首次出现的位置，实际上是希望在找到目标值的同时让left不动而right尽量往左靠，所以，我们让target <= nums[mid]时就让right往左靠。同理，如果我们要找目标值最后出现的位置，实际上是希望在找到目标值的同时让right不动而left尽量往右靠，所以，我们让nums[mid] <= target时就让left往右靠，代码如下：

    public int higherBound(int[] nums, int target) {
        // write your code here
        if (nums == null) return -1;
        int left = 0;
        int right = nums.length;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        if (left - 1 >= 0 && nums[left - 1] == target) return left - 1;
        
        return -1;
    }

需要注意while循环结束后的if条件的判断，由于采用了左闭右开区间，对于lowerBound，如果目标值存在，则left指向最左位置的目标值，如果目标值不存在，则指向目标值应当插入的位置；对于higherBound，如果目标值存在，则left指向最右位置的目标值的下一个位置，如果目标值不存在，则指向目标值应当插入的位置。

每日学习笔记，写于2020-04-30 星期四