如何掌握技术面试中的二分查找变体

2026-06-25 约 594 字预计阅读 3 分钟

二分查找看似简单，大多数候选人能在一分钟内写出基本版本，但二分查找问题仍然是技术面试中最容易出错的题型之一。原因很直接：面试官很少考查原版二分查找，而是测试各种变体，要求精确的边界处理、创造性的搜索空间定义，以及将核心思想应用到非显而易见场景的能力。在 Google、Meta、Amazon 等公司中，大约 20-25% 的编程面试轮次会出现二分查找题目，而且往往伪装成完全不同的问题。

为什么二分查找会难倒资深工程师

二分查找中经典的 off-by-one 错误有着充分的文献记载。Donald Knuth 曾指出，虽然第一个正确的二分查找发表于 1946 年，但第一个无 bug 的实现直到 1962 年才出现。今天的挑战不在于写出正确的基本二分查找，而在于识别一个问题是否可以用二分查找来解决，然后为该特定变体选择正确的边界更新逻辑。

使用 AI 面试助手练习这些变体，可以帮助你在真实的时间压力下培养模式识别能力。当你能在阅读题目的前两分钟内识别出"这是一个对答案进行二分查找的问题"时，你就比其他候选人拥有了巨大的先发优势。

基础：确保模板正确

在深入变体之前，你需要一个万无一失的基础模板。最常见的 bug 来源是循环条件、中间点计算和边界更新之间的不一致。

左闭右闭模板 [lo, hi]：

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

此模板的关键规则：

初始化 hi = len(nums) - 1（两端都包含）
循环条件为 lo <= hi（窗口为空时终止）
更新 lo = mid + 1 或 hi = mid - 1（在此循环条件下绝不能用 lo = mid 或 hi = mid，否则会导致死循环）
使用 lo + (hi - lo) // 2 避免整数溢出

面试技巧： 选定一个模板并始终如一地使用。在面试中途切换 [lo, hi] 和 [lo, hi) 两种约定是引入 bug 的最快方式。

六大核心二分查找模式

模式一：查找第一个/最后一个出现位置

这是最重要的二分查找变体。不是找到目标的任意出现位置，而是需要找到最左边或最右边的那个。

经典题目： 第一个错误的版本、在排序数组中查找元素的第一个和最后一个位置、搜索插入位置。

查找第一个出现位置：

def find_first(nums, target):
    lo, hi = 0, len(nums) - 1
    result = -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            result = mid
            hi = mid - 1  # 继续向左搜索
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result

关键区别： 找到目标时不要立即返回，而是记录下来并继续向相应方向搜索。这一个简单的修改就能解锁一大类问题。

模式二：旋转排序数组

一个在某个枢轴处旋转过的排序数组是最常被考查的二分查找问题之一。核心洞察是：mid 两侧至少有一半是有序的。

经典题目： 搜索旋转排序数组、寻找旋转排序数组中的最小值、搜索旋转排序数组 II（含重复元素）。

策略：

比较 nums[mid] 和 nums[lo] 来确定哪一半是有序的。
检查目标是否落在有序的那一半中。
如果是，搜索那一半；如果不是，搜索另一半。

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:  # 左半部分有序
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:  # 右半部分有序
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

面试技巧： 含重复元素的版本（nums[lo] == nums[mid]）需要退化为 lo += 1，最坏情况时间复杂度降至 O(n)。面试官很喜欢考查这个边界情况。

模式三：对答案进行二分查找

这是最强大也最不直观的模式。不是在给定数组中搜索，而是在可能答案的空间上进行二分查找，并使用可行性检查来引导搜索。

经典题目： 珂珂吃香蕉、分割数组的最大值、在 D 天内送达包裹的能力、制作 m 束花所需的最少天数。

模板：

def min_answer(nums, constraint):
    lo, hi = min_possible, max_possible
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(mid, nums, constraint):
            hi = mid
        else:
            lo = mid + 1
    return lo

如何识别： 如果问题要求满足某个条件的最小值（或低于某个阈值的最大值），并且可行性是单调的（一旦为真，对所有更大的值都为真），你就可以对答案进行二分查找。

面试技巧： 可行性函数才是真正的工作所在。确保它以 O(n) 或 O(n log n) 运行以保持整体复杂度高效。面试官评估你编写干净、正确的可行性检查的能力，不亚于评估二分查找本身。

模式四：矩阵中的二分查找

在排序的二维矩阵中搜索是一维二分查找的直接扩展。关键是将矩阵视为展平的排序数组，并在一维索引和二维坐标之间转换。

经典题目： 搜索二维矩阵、搜索二维矩阵 II、有序矩阵中第 K 小的元素。

对于完全有序的矩阵（每行紧接上一行之后）：

def search_matrix(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    lo, hi = 0, rows * cols - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        val = matrix[mid // cols][mid % cols]
        if val == target:
            return True
        elif val < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

对于行有序且列有序的矩阵： 使用阶梯搜索（从右上角或左下角开始）以 O(m + n) 的时间复杂度替代二分查找。

模式五：峰值查找

在数组或矩阵中查找峰值元素使用了一种乍看反直觉的二分查找方式——数组不需要是有序的。关键观察是：你总是可以通过向更高的邻居方向移动来消除一半的搜索空间。

经典题目： 寻找峰值元素、在二维矩阵中寻找峰值元素。

def find_peak(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo

为什么这有效： 如果 nums[mid] < nums[mid + 1]，那么右侧必定存在一个峰值（序列是递增的，而边界被视为负无穷）。这个保证允许即使没有全局排序也能使用二分查找。

模式六：跨排序集合的中位数和第 K 小元素

查找两个排序数组的中位数或跨排序列表的第 k 小元素使用二分查找来最优地划分元素。

经典题目： 寻找两个正序数组的中位数（困难）、两个排序数组中第 K 小的元素。

核心思想： 在较小的数组上对分割点进行二分查找。对于每个候选分割，检查分割是否有效（左边的所有元素都小于右边的所有元素）。

这被广泛认为是最难的面试题之一。Google 和 Apple 的面试官用它来评估高级和 Staff 级别的候选人。关键是在较短的数组上进行二分查找以最小化复杂度。

常见的致命错误

在 while lo <= hi 中使用 lo = mid。 当 lo == hi == mid 时会导致死循环。如果你需要 lo = mid，必须使用 while lo < hi 并设置 mid = lo + (hi - lo + 1) // 2（向上取整）。

忘记处理空输入。 在开始二分查找之前，始终为空数组或单元素数组添加保护子句。

未考虑中间点计算中的整数溢出。 始终使用 lo + (hi - lo) // 2 而非 (lo + hi) // 2。虽然 Python 原生处理大整数，但在 Java 和 C++ 中这个习惯至关重要，面试官会注意到。

混淆最小化和最大化问题。 对于"找到使…成立的最小值"问题，可行时移动 hi = mid。对于"找到使…成立的最大值"问题，可行时移动 lo = mid（中间点向上取整）。搞反了是一个细微但致命的错误。

如何高效练习

先分类再编码。 写任何代码之前，先确定适用六大模式中的哪一个。仅这一步就能排除大多数错误的解题方向。
用小例子手动推演。 用大小为 1、2、3 的数组追踪你的代码。这些微小的用例能暴露大例子中隐藏的 off-by-one 错误。
在时间压力下练习。 中等难度的二分查找问题应在 10-15 分钟内完成。使用 OfferBull 模拟面试来重现真实场景，在编码的同时解释你的思路。
重点掌握"对答案二分查找"模式。 这是大多数候选人遗漏的模式，它能解锁一大批乍看无解的问题。至少练习五道这个类别的题目。

常见问题

问：我应该始终使用 [lo, hi] 模板吗？ 答：一致性比选择哪个模板更重要。[lo, hi]（左闭右闭）模板最常见也最容易推理。[lo, hi)（左闭右开）模板同样有效但需要不同的边界更新。选定一个并在整个面试过程中坚持使用。

问：如何判断一个问题需要二分查找还是双指针？ 答：二分查找适用于排序或单调结构，能在每一步消除一半的搜索空间。双指针适用于需要找到满足条件的数对或子数组的情况。有些问题两种方法都可以解决，当搜索空间是答案本身时，二分查找通常更简洁。

问：二分查找在系统设计面试中重要吗？ 答：二分查找本身很少出现在系统设计中，但其底层原理——在有序数据中进行对数级搜索——无处不在。B 树、跳表、日志结构合并树，甚至一致性哈希都依赖相同的思想。深入理解二分查找有助于你推理数据库索引和分布式键查找。

将你的面试准备提升到新高度

二分查找是那种有针对性练习就能产生超额回报的主题之一。模式是有限的，边界情况是已知的，一旦你内化了这些知识，你就能发现其他候选人完全忽略的二分查找机会。

立即开始练习：

官方网站： www.offerbull.net
iOS 应用： iPhone/iPad 下载
Android 应用： Android 下载

目录