二分查找与二分思想

二分查找看起来是整个大纲里最简单的算法,却贡献了面试中最稳定的翻车现场:死循环、差一位退出、两个元素的数组返回错误答案。第一课先建立一个能消灭整类 bug 的循环模板——while (left + 1 < right),然后把它拉伸到二分查找的每一个题型家族:第一个/最后一个位置、旋转数组、二维矩阵、未知边界数组,以及直接在答案空间上做二分。

讲算法之前:如何回答任何一道面试题

这节课开场先给了一个适用于所有 coding 题的答题框架。值得背下来,因为面试官打分打的是过程,不只是代码:

1. Clarify——复述题目,确认输入范围、有无重复、是否有序、期望输出。
2. Approach——把候选思路说出来,对比,然后「有意识地」选一个。
3. 函数签名——先写输入、输出、辅助函数的签名,再写函数体。
4. 假设——提前枚举 corner case、edge case、base case。
5. 注释、编码、复查——先写注释骨架,再填代码,最后走一个例子。
6. 复杂度——不等提问,主动收尾说时间和空间。

下面的全部内容,就是把这个框架套在一个算法家族上。注意看第 4 步——corner case——多么频繁地成为二分查找真正的难点所在。

什么时候能用二分?

条件反射的答案是「数组有序时」。正确答案更强:只要存在一个模式,让你每一步都能丢掉一半搜索空间,就能用二分。有序只是这类模式里最常见的一种。

最纯粹的心智模型是一个布尔序列:

1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
              ↑
              找第一个 0——这里没有任何「有序数组」,
              但每次探测都能丢掉一半空间

任何能改写成「找到单调判定翻转的边界」的题都是二分题。First Bad Version 就是这幅图的原题(F F F F T T T T);Sqrt(x) 是这幅图套在 mid > x/mid 上;Wood Cut 是这幅图套在「这个长度能切出 k 段吗?」上。看出翻转边界的形状之后,剩下的就是模板。

笔记里还有一个值得记住的视角:二分查找是二叉搜索树的扁平版本。对 mid 的比较扮演的正是 BST 节点比较的角色——每问一个问题,剪掉一棵子树。这个联系在 第 5 课 讲 BST 时会兑现。

三种循环写法——为什么只留一种

循环有三种标准写法,区别在退出条件和边界移动方式。它们只在一件真正要紧的事上不同:循环结束时留下什么状态。

写法 1:while (left <= right)

边界越过 mid 移动:left = mid + 1、right = mid - 1。指针交错时退出——right 停在 left 左边一格。做纯粹的成员判断(「目标在不在?」)没问题,因为看到目标就直接返回;做找边界的题很痛苦,退出后你得重新推理自己到底要哪个位置,而 +1/-1 的算术正是差一位 bug 的温床。

写法 2:while (left < right)

left == right 时退出——只剩一个幸存者,听起来干净,但恰好有一种情况永远不会在循环里被检验(两针相遇时循环条件已经为假)。你最终还是要对最后一个元素做特判,而且把 left = mid + 1 和 right = mid 混用写对,比看上去难。

写法 3:while (left + 1 < right)——要背的那个

int left = 0, right = nums.length - 1;
while (left + 1 < right) {
    int mid = left + (right - left) / 2;  // 防溢出,永远不写 (left+right)/2
    if (condition(mid)) {
        right = mid;   // 任何地方都没有 +1 / -1——mid 本身仍是候选
    } else {
        left = mid;
    }
}
// 后处理:恰好剩下两个相邻候选
if (isAnswer(left))  return left;
if (isAnswer(right)) return right;
return -1;

循环在 left 与 right 相邻时退出。因为两个赋值都是朴素的 left = mid / right = mid,窗口每轮严格收缩——死循环在结构上不可能发生;又因为 mid 从不被排除,你永远不会越过答案。代价:循环没把活干完,留下两个候选,必须后处理。这笔交易极划算——后处理每道题都是同样两行,而 +1/-1 的推理每道题都不一样。

模板实战:First Bad Version 与 Guess Number

LC 278 First Bad Version 就是翻转边界那幅图的原文照搬:版本序列是 F F F F T T T T,求第一个 T。看模板需要的代码有多短:

public int firstBadVersion(int n) {
    int left = 1, right = n;
    // F F F F F F F T T T T T T T T T — 找第一个 T
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) right = mid;   // mid 可能就是第一个坏版本 → 留住它
        else                    left = mid;
    }
    return isBadVersion(left) ? left : right;
}

LC 374 Guess Number Higher or Lower 是同一副骨架,只是布尔判定换成三向比较——guess(mid) 返回 0/1/-1,遇 0 提前返回。LC 278 能肌肉记忆默写的话,LC 374 只是改个变量名。

第一个与最后一个位置(LC 34)

Search for a Range:在有重复元素的有序数组里找目标的第一个和最后一个下标。两种干净解法,都是 O(log n):

• 模板跑两遍——一遍向左偏(相等时 right = mid)找第一次出现,一遍向右偏(left = mid)找最后一次。
• firstEqualOrGreater 技巧——只写一个辅助函数:找第一个满足 nums[i] >= target 的下标。区间就是 [ f(target), f(target + 1) − 1 ]。一个辅助函数,调两次,零重复逻辑。

public int[] searchRange(int[] nums, int target) {
    if (nums == null || nums.length == 0
        || nums[0] > target || nums[nums.length - 1] < target)
        return new int[]{-1, -1};

    int start = firstEqualOrGreater(nums, target);
    if (nums[start] != target) return new int[]{-1, -1};  // 比如 [5,7,8],target 6

    return new int[]{start, firstEqualOrGreater(nums, target + 1) - 1};
}

private int firstEqualOrGreater(int[] nums, int target) {
    int left = 0;
    int right = nums.length;      // 不是 length-1:target+1 可能比所有元素都大([1],target 1)
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid;
        else                    right = mid;
    }
    return nums[left] >= target ? left : right;
}

边界类问题:Insert Position 与 Peak Element

LC 35 Search Insert Position 是模板加一个三路后处理:循环结束后依次检查 nums[start] >= target、nums[end] >= target,否则返回 end + 1。原始笔记里的批注值得原样复述:等号判断必须留在后处理里,因为数组很小时 while 循环可能根本进不去。后处理不是收尾清扫——它是一条完整的代码路径。

LC 162 Find Peak Element 展示模板在无序数据上工作——判定条件是局部坡度。nums[mid] 在上坡上,右边必有峰;在下坡上,左边必有峰;mid 比两边邻居都大,直接返回。只有两个元素时循环不执行,后处理(返回 start/end 里大的那个)直接给答案。有序从来不是前提;「能丢一半」的论证才是。

反向二分:看不到终点的时候

Search in a Big Sorted Array(LintCode):数组有序,但只能按下标探测,长度未知——越界返回 null。没法写 right = length − 1,那就用倍增把右边界造出来:从 end = 1 开始不断翻倍,直到探测越过目标(返回 null 或值 ≥ target),然后在 [end/2, end] 里跑普通模板。

S E
_ S _ E
_ _ _ S _ _ _ E
_ _ _ _ _ _ _ S _ _ _ _ _ _ E     // 每轮翻倍:O(log answer)
                                  // E 越过目标时,T 被困在 [S, E] 里

倍增阶段花 O(log k),k 是答案的位置,总复杂度仍是对数级。同样的「指数探测 + 二分」出现在扔鸡蛋的讨论里:鸡蛋金贵就一层层试(1 个蛋,O(n) 次);次数金贵就激进探测再二分区间。认出面试官到底想省哪种资源,才是真正的考点。

二维上的二分(LC 74 与 LC 240)

两道长得像、骨子里完全不同的矩阵搜索题:

LC 74 Search a 2D Matrix——每行有序,且每行第一个元素大于上一行最后一个。这说明矩阵是穿着二维外衣的一条有序数组。在下标 0 … rows×cols−1 上二分,再翻译:i = mid / cols、j = mid % cols。纯模板,O(log mn),外加笔记里点名的四个 corner case(matrix 为 null/空、matrix[0] 为 null/空)——那才是真正的面试筛子。

LC 240 Search a 2D Matrix II——行有序、列也有序,但行与行不衔接。它不是拍平的有序数组,直接二分必死。正确工具是阶梯走位:从右上角出发;当前值太小就下移(row++),太大就左移(col--)。每一步永久排除一整行或一整列 → O(m + n)。

旋转有序数组:先分类,再套模板

LC 33 Search in Rotated Sorted Array——有序数组在未知位置旋转过([4,5,6,7,0,1,2])。关键洞察:随便从哪切一刀,至少有一半仍然完整有序。于是每轮问两个问题而不是一个:(1) 哪半边有序?——比较 nums[mid] 和 nums[left];(2) 目标在不在有序那半边的范围里?在就去那边,不在就去另一边。模板的形状原封不动——只是分支条件变多。

while (left + 1 < right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) return mid;

    if (nums[mid] > nums[left]) {            // 左半边 [left..mid] 有序
        if (nums[left] <= target && target < nums[mid])
            right = mid;                     // 目标落在有序半边内
        else
            left = mid;
    } else {                                 // 右半边 [mid..right] 有序
        if (nums[mid] < target && target <= nums[right])
            left = mid;
        else
            right = mid;
    }
}
return nums[left] == target ? left : (nums[right] == target ? right : -1);

LC 81(允许重复)打破了一个假设:当 nums[left] == nums[mid] == nums[right] 时,你真的无法判断哪半边有序——比较不提供任何信息。解法很朴素:窗口缩一格(right--)再试。就这一行,最坏复杂度从 O(log n) 掉到 O(n)(想想 [1,1,1,1,0,1,1])。不等提问主动说出这个退化,是面试里的强信号时刻。

LC 153 / 154 Find Minimum in Rotated Sorted Array——同一家族,判定更精简:拿 nums[mid] 和 nums[right] 比。更小 → 最小值在 mid 或它左边;更大 → 严格在 mid 右边。笔记里标了经典陷阱:要和 right 比,不是 left——如果数组根本没旋转,和 left 比会把你带离最小值。LC 154 加上重复元素,同样的 right-- 药方,同样的 O(n) 最坏情况。

答案空间上的二分

本课最能迁移的思想:没有任何规定说被二分的东西必须是下标。Wood Cut(LintCode):给定木板长度数组和需要的段数 k,求能切出的最大段长。观察单调判定:长度 L 能切出 ≥ k 段,那么比 L 短的任何长度也能——答案取值范围上是 T T T T F F F。二分长度:范围 [1, max(L)],判定 Σ(Lᵢ / mid) ≥ k;因为要的是最大可行值,后处理先测 end 再测 start。

LC 410 Split Array Largest Sum——把数组切成 m 段连续子数组,最小化最大段和。听起来像 DP(也确实有 DP 解法),但答案空间视角更干净:答案落在 [max(nums), sum(nums)];给定一个候选上限,贪心地从左到右扫一遍数出被迫切成几段;可行的上限构成 F F T T T 边界。二分遇上贪心——O(n log(sum))。

public int splitArray(int[] nums, int m) {
    long l = 0, r = 0;
    for (int num : nums) { l = Math.max(l, num); r += num; }  // 答案 ∈ [max, sum]

    while (l + 1 < r) {
        long mid = l + (r - l) / 2;
        if (feasible(mid, nums, m)) r = mid;   // 上限可行 → 试更小的
        else                         l = mid;
    }
    return feasible(l, nums, m) ? (int) l : (int) r;
}

private boolean feasible(long cap, int[] nums, int m) {
    int parts = 1; long total = 0;
    for (int num : nums) {
        total += num;
        if (total > cap) {                // 贪心:装不下才开新段
            total = num;
            if (++parts > m) return false;
        }
    }
    return true;
}

LC 69 Sqrt(x) 是同一家族的迷你版——在 1…x 的取值上二分,判定 mid > x / mid(用除法而不是乘法,躲开溢出)。三道题,一个配方:取值范围 + 单调可行性检查 = 二分。

二分作为子过程

课程收尾的几道题里,二分是更大算法里的一个组件:

• LC 300 Longest Increasing Subsequence——O(n log n) 解法维护一个 tails 数组(每个 LIS 长度对应的最小结尾),对每个新元素二分插入位置。被二分的数组是算法自己建出来的,且构造上保持有序。
• LC 354 Russian Doll Envelopes——二维 LIS。按宽度升序排,宽度相同时高度降序(让相同宽度无法互相嵌套),然后对高度跑 LIS。排序技巧是整道题的灵魂;二分部分直接继承 LC 300。
• LC 302 Smallest Rectangle Enclosing Black Pixels——已知连通黑色区域里的一个像素,用 isEmptyRow / isEmptyColumn 作判定,分别二分四条边界。四次独立的翻转边界搜索,O(m log n + n log m)——图大的时候远胜 flood fill。
• LC 275 H-Index II——引用数已排序,找 citations[i] ≥ length − i 翻转的边界。一道穿着学术马甲的翻转边界题。

刷题清单