二分查找是一种常见的查找算法，他能在有序数组里以 O(logn) 时间复杂度完成查找，是一种很值得掌握的算法。二分查找基本原理很简单，难的是细节处理，第一个二分查找出现在 1946 年，但完全正确的版本直到 1962 年才出现。

我前前后后也刷了挺多二分查找的题，总结出了一些经验，希望他们也能帮助到你。

完善细节的基础版本

先上一个最简单的二分查找：

// 在递增不重复的数组 nums 中查找值为 target 的下标，不存在则返回 -1
public int bsearch(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (nums[mid] < target) {
            low = mid + 1;
        } else if (nums[mid] > target) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

上面的版本是最直观最容易写出来的，不过需要完善一下细节，上面有一个还不够健壮的地方，需要改进下：

// 改进前
int mid = (low + high) / 2;

// 改进后
int mid = low + ((high - low) >> 1);

因为任何数据都需要考虑边界范围，用减法替代加法就不会出现溢出的 bug 了。另外位运算比乘除有性能提升，因此这里也优化了一下，当然你如果不习惯位操作，那只处理溢出问题就足够了。

实际上任何复杂的版本都是基于上面这个，所有复杂版本的分析只要基于这个就行了。至于复杂和变体版本总结出来需要搞懂两点：“收缩区间”和“确定 target”，下面具体来讲。

收缩区间

收缩区间就是指每次二分操作时，收缩上下界。基础版本里的收缩区间逻辑如下：

// 在非空递增不重复的数组 nums 中查找值为 target 的下标，不存在则返回 -1
public int bsearch(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    // 1. 终止条件
    while (low <= high) {
        // 2. 二分点的选择
        int mid = low + ((high - low) >> 1);
        if (nums[mid] < target) {
            low = mid + 1; // 小于时：收缩下边界
        } else if (nums[mid] > target) {
            high = mid - 1; // 大于时：收缩上边界
        } else {
            return mid;
        }
    }
    // 3. 返回值的选择
    return -1;
}

我们发现收缩区间时，上下界两个都没有包含二分点 mid 时：

  1. 终止条件：上下界都能收缩，说明是精确查找，需要判断数组里的每一个数是否满足，因此终止条件是 <=。
  2. 二分点的选择：二分点有“往大取”和“往小取”两种，这里因为上下界都能收缩，实际上两种都行，这里就选用了简单的 “往小取”。
  3. 返回值的选择：因为是精确查找，答案都是在循环体里，如果循环终止就直接返回未找到。

我们再看一个收缩区间时，上下界其中一边包含 mid 的例子：

// 在非空递增不重复的数组 nums 里查找最后一个小于 target 值的下标，不存在则返回 -1
public int bsearch(int[] nums, int target) {
    if (nums[0] >= target) return -1;
    int low = 0, high = nums.length - 1;
    // 1. 终止条件
    while (low < high) {
        // 2. 二分点的选择
        int mid = low + ((high - low + 1) >> 1);
        if (nums[mid] < target) {
            low = mid; // 小于时：收缩下边界，注意这里需要包含 mid
        } else {
            high = mid - 1; // 大于等于时：收缩上边界
        }
    }
    // 3. 返回值的选择
    return low;
}

返回 -1 的情况属于特例，可以很简单的处理掉，先抛开不看。我们主要还是看那三点逻辑：

  1. 终止条件：因为出现上下界收缩包含 mid 时，说明找的是近似值，此时剩下最后一个数就不用再判断直接就是答案。而如果用 <= 就可能会出现死循环。
  2. 二分点的选择：因为下边界会出现不收缩的情况，因此每次取二分点需要往大取，这样才能每次保证区间每次得到收缩。加一个比除数 2 小 1 的数，就能保证结果往大取。
  3. 返回值的选择：因为出现上下界收缩包含 mid 时，说明找的是近似值。这里需要将区间不断缩小成只有一个元素，这个元素（low 等于 high）就是答案。而基础版本是精确查找，循环体外代表没有答案。

确定 target

基础版本里面都有个固定的 target 值，实际上二分查找还可能不显式提供出来，此时需要我们先推理确定 target。我们同样直接上例子讲解：

// 在非空相邻不等的数组 nums 种，找到峰值下标，其中 nums[-1] = nums[n] = -∞
public int findPeakElement(int[] nums) {
    int low = 0, high = nums.length - 1;
    while (low < high) {
        int mid = low + ((high - low) >> 1);
        if (nums[mid] < nums[mid + 1]) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

这里的 target 实际上就是下一个元素 nums[mid + 1]，因为只要跟这个元素比较，就能知道如何收缩区间。

顺便再提一下上一节 “收缩区间” 的知识。因为这里收缩上边界时需要包含 mid，因此：终止条件用 <，二分点的选择是“往小取”，返回值的选择是收缩成的最后一个元素。

总结

二分查找场景较为苛刻，要求数据为顺序表结构，只适合没有增删操作的静态数据场景，因此大部分场景下我们都会用哈希表和二叉树查找代替二分查找。 这也就使得真实场景里，需要二分查找的都是复杂场景（求近似值，变体），因此掌握复杂场景的二分查找写法才有实际价值。

本文将所有二分查找算法抽象成了 “收缩区间” 和 “确定 target” 两点，后面写二分查找直接考虑清楚这两点，然后依葫芦画瓢代码就能出来了。