二分算法全攻略：从查找数值到二分答案的质变

二分算法全攻略：从查找数值到二分答案的质变

在算法面试和机试（如 ECNU 考研机试）中，二分算法（Binary Search） 是出现频率极高、也是极容易写出 Bug 的基础算法之一。它的本质不仅仅是在有序数组中找一个数，更是利用单调性来缩小搜索范围的强大思维工具。

本文将带你从基础的“红蓝染色法”二分查找，进阶到化腐朽为神奇的“二分答案”。

一、 二分查找：红蓝染色法的统一逻辑

很多同学在写二分时会被 left <= right 还是 left < right 困扰。灵神推荐的开区间二分（(left, right)） 能完美避开所有边界坑。

核心模板：寻找到第一个满足条件的下标

以寻找 lower_bound（第一个 $\ge x$ 的数）为例：

1
2
3
4
5
6
7
8
9
10
11
12
public int lowerBound(int[] nums, int target) {
    int left = -1, right = nums.length; // 开区间 (left, right)
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid; // 红色：不满足条件，向右压缩
        } else {
            right = mid; // 蓝色：满足条件，向左压缩
        }
    }
    return right; // 最终只有蓝色区域满足 >= target，返回第一个蓝色的下标
}

经典案例：34. 在排序数组中查找元素的第一个和最后一个位置

  • 思路：
    • 第一个位置 = lowerBound(target)
    • 最后一个位置 = lowerBound(target + 1) - 1
  • 注意点：如果 lowerBound(target) 返回的下标越界，或者该下标处的值不等于 target，则说明数组中不存在该元素。

二、 二分答案：化“找数”为“做题”

“花费一个 log 的时间，增加了一个条件。” 这是二分答案的核心魅力。如果题目求的是“最大值的最小”或“最小值的最大”，且具有单调性，那么二分答案就是必杀技。

核心逻辑：从虚拟数组中找界限

假设答案范围在 [low, high] 之间，我们可以构建一个虚拟的布尔数组： [check(low), check(low+1), ..., check(high)] 由于单调性，这个数组必然呈现为 [T, T, ..., T, F, F, ..., F] 或反之。我们的任务就是在这个虚拟数组上做二分查找。

典型案例 1：求最小（满足条件的左边界）

875. 爱吃香蕉的珂珂

  • 核心代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    public int minEatingSpeed(int[] piles, int h) {
        int left = 0, right = 1_000_000_000;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(mid, piles, h)) right = mid;
            else left = mid;
        }
        return right;
    }
  • 单调性：速度越快，耗时越短。
  • check(mid)：计算以速度 mid 吃完所有香蕉的总用时 $\le H$。

典型案例 2：最大化最小值（求最大符合条件的下界）

1552. 两球之间的磁力

  • 核心代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int left = 1, right = position[position.length - 1] - position[0] + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(mid, position, m)) left = mid;
            else right = mid;
        }
        return left;
    }
  • 核心思路：二分查找“最小磁力”。如果以距离 mid 能放下 m 个球，说明 mid 可能还可以更大，因此更新 left = mid。
  • 注意点：check 函数通常使用贪心策略来放置球。

典型案例 3：最小化最大值（求最小符合特的上界）

410. 分割数组的最大值

  • 核心代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public int splitArray(int[] nums, int k) {
        long left = Arrays.stream(nums).max().getAsInt() - 1;
        long right = Arrays.stream(nums).sum() + 1;
        while (left + 1 < right) {
            long mid = left + (right - left) / 2;
            if (check(mid, nums, k)) right = mid;
            else left = mid;
        }
        return (int) right;
    }
  • 核心思路：二分查找“各子数组和的最大值”。如果这个最大值 mid 能让数组分割成 $\le k$ 个子数组，说明 mid 还可以更小，更新 right = mid。

三、 实战高阶：ECNU2024-基建高手

这是今天遇到的一道极具代表性的机试题。

题目复盘

  • 描述：有 $n$ 条生产线，第 $i$ 条线每 $a_i$ 分钟产出一块赤金。求产出至少 $k$ 块赤金的最早时间 $T$。
  • 数据范围：$n, k, a_i$ 均可达 $10^9$。
  • 为什么必须二分？
    • 时间 $T$ 可能非常大（可达 $10^{18}$），求 $LCM$ 或暴力模拟必然超时或溢出。
    • 随着时间 $T$ 的增加，产出总数 $f(T)$ 严格不减（单调性）。

Java 实现模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
static void solve() throws Exception {
    int n = readInt();
    long k = readLong();
    long[] a = new long[n];
    for (int i = 0; i < n; i++) a[i] = readLong();

    long low = 0, high = (long) 2e18; 
    long ans = high;
    while (low <= high) {
        long mid = low + (high - low) / 2;
        if (check(mid, a, k)) {
            ans = mid;
            high = mid - 1; 
        } else {
            low = mid + 1;
        }
    }
    out.println(ans);
}

static boolean check(long T, long[] a, long k) {
    long total = 0;
    for (long val : a) {
        total += T / val; 
        if (total >= k) return true; // 极其重要：防止溢出
    }
    return total >= k;
}

四、 特殊二分场景：旋转数组与峰值

并非只有全有序数组才能二分，只要存在局部单调性或二段性即可。

旋转数组的最小值：153. 寻找旋转排序数组中的最小值

  • 核心代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public int findMin(int[] nums) {
        int left = -1, right = nums.length - 1;
        int target = nums[nums.length - 1]; // 以末尾元素为基准
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) right = mid;
            else left = mid;
        }
        return nums[right];
    }
  • 二段性：旋转数组可以分为两段有序序列。通过与 nums[n-1] 比较，可以判定 mid 落在左半段（较大值区）还是右半段（最小值所在区）。

五、 总结：二分的三种境界

  1. 境界一：找数。在有序数组中找特定值，重点是边界控制。
  2. 境界二：求极限。
    • 求最小（满足要求的第一个）：对应 right = mid。
    • 求最大（满足要求的最后一个）：对应 left = mid。
  3. 境界三：判可行性（二分答案）。将难题转化为一个 check(x) 函数，通过枚举（二分）答案来验证可行性。

💡 考研机试避坑贴士：

  • 上界溢出：二分答案时，high 的设置要大胆（如 $10^{18}$），但 low + high 可能溢出，务必使用 mid = low + (high-low)/2。
  • 早停策略：在 check 函数累加过程中，一旦满足条件立即 return true，防止中间过程溢出。

希望这篇笔记能帮你打通二分的任督二脉！下次遇到 $10^9$ 级别的数据且有单调性，请直接开启二分模式。