二分查找

基本概念

二分查找用于在有序的数组中快速找到目标值，使用的前提是有序，这个顺序可以有很多变形，总结起来就是这个数组中的元素要按照一定的规律排列。具体做法就是看数组中间的元素是否满足要求，如果不满足，则根据有序的前提，这个数组中一半的元素一定不满足要求，从另一半中继续看中间元素是否满足，直到找到目标。

基础实现

class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right)/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;
    }
}

实现细节

二分查找有以下几个细节

• while中的判断条件是left<right 还是left<=right
• 未命中target的情况下，left的值取mid+1还是mid
• 未命中target的情况下，right的值取mid-1还是mid
• right 初始的值是等于len还是len-1
  上述三点细节其实都对应着一个定义，即你想找的target和边界left，right的关系是什么。

如果target可能在右边界上，即target in [left, right] 则 应该写成上面的写法，left<= right, left = mid+1, right = mid-1, right init = len-1

如果target不能在右边界上，即target in [left,right) 则应该像下面这样写 left<right, left = mid+1, right = mid, right init= len

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

上述两种写法都是正确的，但一定注意搭配好各个参数，否则就会死循环。

区别在于，当没有命中的时候，左闭右开的写法可以正好定位到缺失元素的位置上，即左右边界刚好收敛到这个点上。

进阶情况

有重复元素，如果要找第一个或最后一个target

对应lc34

这种情况下多想一步，先按照上述实现标准的二分查找

如果能找到target，此时如果把这个target当作新的右边界，则意味着想继续看看命中的左边还能不能命中，就是在找左边的第一个target。

同理，如果把这个target当成左边界，则是在看命中的右边还能不能命中，就是在找最后一个命中了。

没有命中，找元素应该加在哪里

对应lc35

还是标准的二分查找，区别在于最终搜索结束之后，左右边界应该刚好收敛在缺失值应该被加入的位置上。这时只有左闭右开的写法是满足条件的。

有序的数组进行变异

核心难点在于找到这个有序的数组的遍历方式，不论以何种形式出现，这个数组按照某种规则进行遍历一定是有序的，在此情况下就可以进行二分查找了。

比如lc33和lc153

都是把有序数组做了一次旋转，旋转后肯定有一半是有序的，那这一半可以二分，另一半递归进行操作即可。

lc74

对一个二维数组，其每一行和每一列都是有序的，则整体上从右上角看是一个二叉搜索树，依赖这个特性进行二分搜索即可。