算法-二分查找解析

只要坚持往正确的方向前进，终会找到答案

前言

阅读本文，你可以理解：二分查找算法原理，相关变种问法和一些场景下的衍生应用

经典二分查找算法

二分查找算法 最经典的场景是在一个 有序数组中，查找目标值所在的下标(若存在)
我们有长度为 $n$ 的数组 $a_0,...,a_i,...,a_j,...,a_{n-1}$，并且对于任意一对下标 $i < j$ ，我们有 $a_i \le a_j$
输入： $a_0,...,a_{n-1}$, $target$
输出： $pos$ (满足 $a_{pos} = target$ (若存在多个返回任意一个)，若不存在则返回 -1)

输入：[1,5,9,10], 9
输出：2 // 9 所在的数组下标为 2

先来看朴素的做法：枚举数组中的每一个元素，判断元素是否为 $target$，如果是则返回其数组下标，若都不存在则返回 -1
这种做法我们需要枚举每一个元素来判断是否存在，时间复杂度为 $O(n)$
题目告知我们 $a_i$ 是一个有序数组，我们是否可以利用这个特性来帮助我们减少判断的次数？
我们可以通过有序数组得知一个事实：在 $a_i$ 左边的数字一定不比它大，在 $a_i$ 右边的数字一定不比它小

$$\left\{\begin{matrix} a_x \le a_i,(x < i) \\ a_i \le a_x,(i < x) \end{matrix}\right.$$

那么对于长度为 $n$ 的数组 $a_i$ 来说：
若 $target = a_x$，那么返回结果
若 $target > a_x$，那么结果不可能位于 $a_0,...,a_x$，此时我们可以跳过对 $a_0,...,a_x$ 的判断，在 $[x+1,n-1]$ 这个范围内进行查找
若 $target < a_x$，那么结果不可能位于 $a_x,...,a_{n-1}$，此时我们可以跳过对 $a_x,...,a_{n-1}$ 的判断，在 $[0,x-1]$ 这个范围内进行查找
以上的步骤，我们可以更通用的表达为：
对于给定的数组 $a_{left},...,a_{right}$，我们需要查找值 $target$ 是否在 $[left,right]$ 这个区间中，
为了使得判断次数的期望最低，每次迭代我们 取 $left$ 和 $right$ 中间位置的值 来和 $target$ 来对比，
每次对比完后维护 $target$ 可能存在的新区间，通过不断缩减区间范围，直到 $left > right$ 为止，这时可以得出答案
为了便于理解，我们需要注意的是：每次操作过后，$target$ 必定在 $[left,right]$ 这个区间中
因我们只需对每个给的的区间，只取中间值来进行判断，其时间复杂度为 $O(log_2 N)$
代码如下：

int binary_search(int[] a, int target) {
    int left = 0, right = a.length - 1;
    while (left <= right) {
        // 这里常见为 (left + right) >> 1，但需考虑溢出的情况
        int mid = (left + right) >>> 1;
        if (a[mid] == target) return mid;
        else if (a[mid] < target) left = mid + 1; // 这种情况下，结果一定位于(若存在) [mid+1, right]
        else if (a[mid] > target) right = mid - 1; // 这种情况下，结果一定位于(若存在) [left, mid -1]
    }
    return -1; // 如果找不到，返回 -1
}

另一点值得注意的是，我们在计算 $[left,right]$ 中间的值时，使用的是 『>>>』 而非 『>>』，是为了处理溢出可能^[1]

寻找边界值

经典二分的实现比较简单且容易理解，但在实际场景中，我们可能会需要处理各种变种，而其中的细节是魔鬼，及其容易出错，接下来会就这个方面展开阐述

求小于 target 的最大值

我们有长度为 $n$ 的数组 $a_0,...,a_i,...,a_j,...,a_{n-1}$，并且对于任意一对下标 $i < j$ ，我们有 $a_i \le a_j$,
输入： $a_0,...,a_{n-1}$, $target$
输出： $max(pos)$ (满足 $a_{pos} < target$，即小于 $target$ 的最大值的最大下标, 若不存在返回 -1)

输入：[3,3,9,10], 9
输出：1 // 小于 9 的最大值为 3，其最大下标为 1

我们依然可以使用类似经典二分的逻辑来跳过不必要的判断，不过为了得到小于目标的最大值，在迭代过程中会有一些变化，我们需要记录满足条件的答案：
若 $target > a_x$，那么结果不可能位于 $a_0,...,a_{x-1}$，此时我们可以跳过对 $a_0,...,a_{x-1}$ 的判断，我们记录 $x$ 作为答案，并在 $[x+1,n-1]$ 这个范围内继续查找
若 $target < a_x$，那么结果不可能位于 $a_x,...,a_{n-1}$，此时我们可以跳过对 $a_x,...,a_{n-1}$ 的判断，并在 $[0,x-1]$ 这个范围内继续查找
若 $target = a_x$，同上

通过对比可能发现，整体的逻辑没有发生太大改变，只是多了一个记录答案的步骤
代码如下：

int binary_search_less_target(int[] a, int target) {
    int left = 0, right = a.length - 1, ans = -1;
    while (left <= right) {
        // 这里常见为 (left + right) >> 1，但需考虑溢出的情况
        int mid = (left + right) >>> 1;
        if (a[mid] < target) {
            // 这种情况下，结果可能还位于 [mid + 1, right]
            ans = mid;
            left = mid + 1;
        } else right = mid - 1; // 这种情况下，结果一定位于(若存在) [left, mid - 1]
    }
    return ans;
}

相比于经典二分，其一些边界处理的细节差异有以下几点：

1. 当 $a_{mid} = target$ 时对右端点维护改为了 $right = mid - 1$
   1. 这是因为目标发生变化，我们需要求小于 $target$ 的最大值而不是求 $target$
2. 新增了变量 $ans$ 用来记录符合 $a_{mid} < target$ 条件的最大下标

求小于等于 target 的最大值

我们有长度为 $n$ 的数组 $a_0,...,a_i,...,a_j,...,a_{n-1}$，并且对于任意一对下标 $i < j$ ，我们有 $a_i \le a_j$,
输入： $a_0,...,a_{n-1}$, $target$
输出： $max(pos)$ (满足 $a_{pos} <= target$，即小于等于 $target$ 的最大值的最大下标, 若不存在返回 -1)

输入：[3,3,9,9,10,10], 8
输出：2 // 小于等于 8 的最大值为 3，其最大下标为 2

我们在小于 target 的最大值的解法上，只对 $target = a_x$ 进行稍加修改为 $target > a_x$ 的处理逻辑即可
若 $target > a_x$，那么结果不可能位于 $a_0,...,a_{x-1}$，此时我们可以跳过对 $a_0,...,a_{x-1}$ 的判断，我们记录 $x$ 作为答案，并在 $[x+1,n-1]$ 这个范围内继续查找
若 $target = a_x$，同上
若 $target < a_x$，那么结果不可能位于 $a_x,...,a_{n-1}$，此时我们可以跳过对 $a_x,...,a_{n-1}$ 的判断，并在 $[0,x-1]$ 这个范围内继续查找

int binary_search_less_or_equal_target(int[] a, int target) {
    int left = 0, right = a.length - 1, ans = -1;
    while (left <= right) {
        // 这里常见为 (left + right) >> 1，但需考虑溢出的情况
        int mid = (left + right) >>> 1;
        if (a[mid] <= target) {
            ans = mid;
            left = mid + 1; // 这种情况下，结果一定位于(若存在) [mid + 1, right]
        } else right = mid - 1; // 这种情况下，结果一定位于(若存在) [left, mid - 1]
    }
    return ans;
}

总结

以上的几个样例，我们的操作逻辑看起来都非常相似：

1. 为了使得判断次数的期望最低，我们每次取查询区间 $left$ 和 $right$ 的中值 $mid$
2. 取 $a_{mid}$ 和 $target$ 进行判断，并维护左右端点，缩减区间，记录答案
   • 若 $target > a_{mid}$，维护左端点为 $mid + 1$，如果满足目标则记录为答案
   • 若 $target < a_{mid}$，维护右端点为 $mid - 1$，如果满足目标则记录为答案
   • 若 $target = a_{mid}$，按照目标来维护左右端点，如果满足目标则记录为答案

它比朴素方法要快的原因在于：

• 利用有序数组的特性来跳过不必要的判断
• 每次迭代维护答案可能位于的 $[left,right]$ 区间，将这个区间分为两部分，每次迭代必然选择一边，使得区间缩减一半
• 为了使得判断次数的期望最低，每次取相对区间 $mid$ 位置的来判断

衍生应用

求单峰函数的极值点

我们有长度为 $n$ 的数组 $a_i$，数组满足 $a_0 < a_1 < ... < a_{i-1} < a_i > a_{i+1} > ... > a_{n-1}$
需要输出满足上述条件的 $i$ 的值

输入：[3,4,5,1]
输出: 2 // 值为 5 的下标为 2

这道题的解法我们依然可以参考经典二分的解法，通过总结出数组的特性，我们先选取任意一点，通过判断和目标的差距的情况，来决定左右端点的偏移
我们选取任意一点 $x$，则有以下几种情况：

• 若 $a_{x-1} < a_x > a_{x+1}$，$x$ 即为需要的答案
• 若 $a_x < a_{x+1}$，那么所求答案必然在 $[x + 1,n - 1]$
• 若 $a_x > a_{x+1}$，那么所求答案必然在 $[0, x - 1]$

int compare(int[] nums, int posL, int posR) {
    if (posL == -1) return -1;
    else if (posR == nums.length) return 1;
    else return nums[posL] - nums[posR];
}

public int findPeakElement(int[] nums) {
    int l = 0, r = nums.length - 1, ans = -1;
    while (l <= r) {
        int m = (l + r) >>> 1;
        if (compare(nums, m - 1, m) < 0 && compare(nums, m, m + 1) > 0) {
            ans = m;
            break;
        }
        if (compare(nums, m, m + 1) < 0) {
            l = m + 1;
        } else r = m - 1;
    }
    return ans;
}

这种方法其实也被称作三分^[2]

分数规划

分数规划通常求分数的极大/小值
对于给定 $a_i$ 和 $b_i$, 我们有 $w_i \in \left \{ 0,1 \right \}$，最小化或最大化

$$\LARGE \frac{\sum_{i=0}^{n-1}a_i w_i}{\sum_{i=0}^{n-1}b_i w_i }$$

这个问题的通用解法是二分，我们来看公式，先假定它的值为 $x$，若它不是最大值，那么必然有

$${\LARGE \begin{array}{c} {\huge \frac{\sum_{i=0}^{n-1}a_i w_i}{\sum_{i=0}^{n-1}b_i w_i } \gt x } \\ \\ \Rightarrow \sum_{i=0}^{n-1}a_i w_i - x \sum_{i=0}^{n-1}b_i w_i \gt 0 \\ \\ \Rightarrow \sum_{i=0}^{n-1}w_i (a_i - b_i x) \gt 0 \end{array} }$$

因为 $w_i \in \left \{ 0,1 \right \}$，对于以上公式来说：

• 当 $(a_i - b_i x) > 0$ 时，对于结果才有正向贡献，此时我们令 $w_i = 1$
• 当 $(a_i - b_i x) < 0$ 时，对于结果没有正向贡献，此时我们令 $w_i = 0$

因此我们对于一个给定的 $x$, 可以判断它是否为最大值，我们令：

$${\LARGE f(x) = \sum_{i=0}^{n-1}w_i (a_i - b_i x)}$$

且看这个函数的性质：单调性^[3]，为何要看单调性？我们再来回想一下经典二分中，正式因为有序数组具有单调性(随着 $a_x <= a_{x+1}$)，因此我们可以在数组上进行二分
如果我们可以求得函数的单调性，便也可以在 $f(x)$ 上进行二分

我们可以使用导数^[4]来研究函数单调性，我们对 $f(x)$ 进行求导，得 ${f(x)}’ = -1 $，便得到一个比较重要的特性：函数 $f(x)$ 是单调递减的，

随着 $x$ 递增，$f(x)$ 递减，随着 $x$ 递减，$f(x)$ 递增
因此可以求解出以下三种情况：

• 若 $f(x) = 0$，说明 $x$ 即为答案
• 若 $f(x) > 0$，说明答案在 $[x,right]$ 这个区间
• 若 $f(x) < 0$，说明答案在 $[left,x]$ 这个区间

聪明的你可能会发现我们可以在函数上进行二分，因为函数本身也是『有序』的，我们可以在有序的东西上进行二分

boolean check(int[] a, int[] b, int[] w, double mid) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] - mid * b[i] > 0)
            return true;
    }
    return false;
}

double fractionPlan(int[] a, int[] b, int[] w) {
    double eps = 1e-6;
    double left = 0, right = 1e9;
    while (right - left > eps) {
        double mid = (left + right) / 2;
        if (check(a, b, w, mid)) left = mid;
        else right = mid;
    }
    return left;
}

一些需要注意的点：

• 因为数据存储的精度问题，我们认为当两个数小于某个阈值，比如 1e-6 时，它们相等
• 因为函数是具有单调性的，我们每次迭代可以维护并缩小左右端点，使得区间逐渐逼近答案

我们的 $check$ 方法实现的就是 $f(x)$ 的逻辑，这个不仅局限于本题，
而且根据不同的题目要求，$f(x)$ 里实现的逻辑可以是任意的，比如：

• 贪心
• 动态规划
• 最小生成树
• 枚举
• 等等等。。。。

至于这道题的分数规划可能还有一些其他的问法：

• 限制最多可以选择 K 个物品
• 限制分子或分母不能超过 W
• 等等等。。。。

总结

通过以上几道例题，特别是分数规划这道题，我们总结出可以使用二分的情况：对于 $f(x)$，对于给定的定义域输入，我们有小于等于 2 个单调性输出，那么我们就可以使用二分求解
比如求单峰函数的极值点这道题，假设 $ans$ 为我们要求的答案，我们有两个单调性：

• $i < ans$，它是单调递增的，此时 ${f(x)}' > 0$
• $i > ans$，它是单调递减的，此时 ${f(x)}' < 0$

而很多时候，我们需要对题目做一些转换，以确定其单调性，才能判断是否可以进行二分
分数规划这道题中，我们做了一个值的假设，对公式进行转换，再抽象出 $f(x)$，判断其单调性，对其按照单调性的特点来二分
这其中比较困难的两步在于：

• 解析题目，做公式变换，转换出函数 $f(x)$，求函数单调性
• 函数 $f(x)$ 中奇奇怪怪的实现

至此，本文结束，希望通过本文，可以给你带来一些收获

---

1. 二分算法的破绽, Nearly All Binary Searches and Mergesorts are Broken, AI Google Blog ↩︎

2. 三分法 - OI-WIKI ↩︎

3. 单调性, 百度百科 ↩︎

4. 求导, 百度百科 ↩︎