LeetCode（五）：二分查找

二分查找看似简单，实则容易出错。核心思想就是每次把搜索范围缩小一半，但在实际编写时——尤其是在面试这种高压环境下——各种边界条件、死循环和返回值错误等问题就会暴露出来。本文不重复罗列模板代码，而是聚焦于解释模板设计背后的逻辑，即那个核心不变量。只要抓住了这个不变量，那些让人纠结的细节——比如用 < 还是 <=，right = mid 还是 right = mid - 1——就不再是靠死记硬背的东西，而是可以自然推导出来的结果。

一、心智模型：维护一个不断缩小的区间#

二分查找的本质是一个逐步缩小搜索区间的问题。我们用两个指针 l 和 r 标记当前可能包含答案的区间，每次取中点 m 检查 nums[m] 的值，然后根据这一信息果断舍弃一半的元素。上图展示了一个典型例子：长度为 16 的有序数组，目标值是 23，经过四次迭代后，搜索窗口从 16 缩小到 1。

整个算法正确性的基石，是始终维护以下不变量：

不变量：如果目标存在，它在每次迭代开始时一定位于当前区间 [l, r]（或 [l, r)，取决于约定）内。

只要这条不变量始终成立，算法就是正确的。一旦某一步破坏了它——比如在寻找第一个等于目标值的位置时，遇到 nums[m] == target 却直接将右边界设为 r = m - 1——你就已经把答案丢掉了，后续的搜索毫无意义。

为什么二分查找的时间复杂度是 $O(\log n)$ ？经过 $$k$$ 轮迭代后，剩余区间最多还有 $\lceil n / 2^k \rceil$ 个元素，因此只需 $k = \lceil \log_2 n \rceil$ 次迭代就能将区间缩小到一个元素。即使面对十亿个元素，也只需要大约 30 次比较——这正是数据库索引、文件系统和 git bisect 等工具依赖它的根本原因。

二分查找的真正适用条件并非“数组有序”，而是“判定条件具有单调性”：只要你能写出一个布尔函数 feasible(x)，其返回值随着 x 增大恰好从 False 翻转为 True（或相反），就可以用二分查找定位这个翻转点。本文后面提到的“答案空间二分”正是基于这一思想。

二、基础模板：闭区间 `[l, r]`#

最简单的场景是在有序数组中找任意一个等于 target 的下标，找不到则返回 -1。这里我们采用闭区间 [l, r] 和循环条件 l <= r：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def binary_search(nums, target):
    """返回任意一个 nums[i] == target 的下标，找不到返回 -1。"""
    l, r = 0, len(nums) - 1
    while l <= r:
        m = l + (r - l) // 2     # 防止 l + r 溢出（C++/Java 必备习惯）
        if nums[m] == target:
            return m
        if nums[m] < target:
            l = m + 1            # target 肯定在右半边
        else:
            r = m - 1            # target 肯定在左半边
    return -1

只需掌握以下三点：

初始边界：r = len(nums) - 1，因为 r 是闭区间的右端点，必须包含在内。
循环条件：l <= r，因为当且仅当 l <= r 时，区间 [l, r] 非空。
更新规则：当 nums[m] != target 时，m 这个位置显然不是答案，因此通过 m + 1 或 m - 1 将其排除。

中点公式 m = l + (r - l) // 2 在数学上等价于 (l + r) // 2，但前者不会因 l + r 过大而溢出。虽然 Python 的整数不会溢出，但养成这个习惯对将来写 C++ 或 Java 大有裨益。

LeetCode 704 —— 二分查找#

给定一个按升序排列的整数数组 nums 和一个目标值 target，在数组中搜索 target，存在则返回下标，否则返回 -1。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            m = l + (r - l) // 2
            if nums[m] == target:
                return m
            if nums[m] < target:
                l = m + 1
            else:
                r = m - 1
        return -1

边界情况完全无需特殊处理：空数组时 r = -1，循环体不会执行，直接返回 -1；单元素数组时 l == r == 0，循环恰好执行一次，逻辑自然成立。

三、边界模板：找第一个或最后一个位置#

许多问题不仅要求判断目标是否存在，还要求找到第一个或最后一个满足条件的位置，甚至插入位置。基础模板无法胜任，因为在 nums[m] == target 时不能立即返回——左边可能还有更早的匹配，右边也可能还有更晚的。

上图展示了两套模板在 nums = [1, 2, 5, 5, 5, 5, 8, 9]、target = 5 上的运行过程。代码几乎完全相同，唯一的区别在于比较符是否严格。

左边界：找到第一个 `nums[i] >= target` 的位置#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def left_bound(nums, target):
    """半开区间 [l, r)，返回最左插入位置。"""
    l, r = 0, len(nums)
    while l < r:
        m = l + (r - l) // 2
        if nums[m] < target:
            l = m + 1            # m 太小，丢掉
        else:
            r = m                # m 可能是答案，保留
    return l                     # 循环结束时 l == r

有三点必须严格遵守：

r = len(nums)，而非 len(nums) - 1。我们使用半开区间 [l, r)，这样才能自然表示“应插入到末尾”的情况（此时答案为 l = len(nums)）。
l < r，与半开区间约定一致：[l, r) 在 l == r 时为空。
r = m，而非 m - 1。当 nums[m] >= target 时，m 本身可能是答案，不能排除。

循环结束后，l 即为第一个满足 nums[i] >= target 的下标。若要转化为“第一次出现 target”，需额外验证：l < len(nums) and nums[l] == target。

右边界：找到最后一个 `nums[i] <= target` 的位置#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def right_bound(nums, target):
    """半开区间 [l, r)，返回最后一个匹配的下标 + 1。"""
    l, r = 0, len(nums)
    while l < r:
        m = l + (r - l) // 2
        if nums[m] <= target:
            l = m + 1            # 继续往右找
        else:
            r = m
    return l - 1                 # 实际答案要减 1（不存在时通过合法性检查兜底）

骨架与左边界几乎一致，唯一区别是将 < 替换为 <=。循环结束后，l 是第一个满足 nums[i] > target 的位置，因此 l - 1 才是最后一个满足 nums[i] <= target 的位置。同样需要验证：l - 1 >= 0 and nums[l - 1] == target。

LeetCode 35 —— 搜索插入位置#

给定一个排序数组 nums 和一个目标值 target，返回目标值的索引；若不存在，则返回它应被插入的位置。要求时间复杂度为 O(log n)。

这题直接套用左边界模板：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        l, r = 0, len(nums)
        while l < r:
            m = l + (r - l) // 2
            if nums[m] < target:
                l = m + 1
            else:
                r = m
        return l

以 nums = [1, 3, 5, 6]、target = 2 为例：

第一次迭代：m = 2，nums[2] = 5 >= 2，故 r = 2；
第二次迭代：m = 1，nums[1] = 3 >= 2，故 r = 1；
第三次迭代：m = 0，nums[0] = 1 < 2，故 l = 1。

此时 l == r，返回 1。将 2 插入下标 1 后，数组变为 [1, 2, 3, 5, 6]，依然有序。

LeetCode 34 —— 在排序数组中查找元素的第一个和最后一个位置#

给定升序数组 nums 和目标值 target，找出其首次和末次出现的位置；若不存在，返回 [-1, -1]。要求 O(log n) 时间。

结合左右边界模板并验证即可：

 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
class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        def left_bound():
            l, r = 0, len(nums)
            while l < r:
                m = l + (r - l) // 2
                if nums[m] < target:
                    l = m + 1
                else:
                    r = m
            return l

        def right_bound():
            l, r = 0, len(nums)
            while l < r:
                m = l + (r - l) // 2
                if nums[m] <= target:
                    l = m + 1
                else:
                    r = m
            return l - 1

        lo = left_bound()
        if lo == len(nums) or nums[lo] != target:
            return [-1, -1]
        return [lo, right_bound()]

LeetCode 278 —— 第一个错误的版本#

版本号从 1 到 n，某个版本起开始出错，之后所有版本均错误。给定 API isBadVersion(version)，找出第一个错误版本，尽量减少 API 调用次数。

同样是左边界模板，只不过操作对象是黑盒函数 isBadVersion(v)，它从 False 单调翻转为 True。我们搜索的是这个谓词的翻转点，而非数组本身：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def firstBadVersion(self, n: int) -> int:
        l, r = 1, n
        while l < r:
            m = l + (r - l) // 2
            if isBadVersion(m):
                r = m            # m 可能是第一个坏版本
            else:
                l = m + 1        # m 是好的，继续往右找
        return l

这是最清晰的例子：二分查找的本质是利用单调性，数据是数组还是 API 并不重要。

四、两种区间约定，选一种用到底#

第二节使用闭区间 [l, r]，第三节使用半开区间 [l, r)。两种写法都正确，但在同一函数中混用会导致死循环。

上图将两种约定并排运行，每步下方的括号清晰展示了区别：闭区间 [l, r] 包含右端点，半开区间 [l, r) 不包含。配对规则如下：

区间约定	初始 `r`	循环条件	`r` 更新方式
闭 `[l, r]`	`len(nums)-1`	`l <= r`	`r = m - 1`
半开 `[l, r)`	`len(nums)`	`l < r`	`r = m`

选定一种约定后，请坚持到底。最常见的错误是 l < r 配 r = m - 1：当区间缩至 [l, l] 时，m = l，更新后 r = l - 1 < l，循环退出，但可能已跳过答案。更糟的是 l <= r 配 r = m：当 l == r == m 时，r = m = l，循环永不终止。

五、旋转数组：还能不能二分？#

前面讨论的数组都是有序的，但旋转数组虽整体无序，却保留了一个关键性质：从任意位置切开，至少有一半是有序的。这足以支撑二分查找。

上图展示了在 nums = [4, 5, 6, 7, 0, 1, 2] 中搜索 0 的过程。每一步先判断哪一半有序（通过比较 nums[l] 与 nums[m]），再检查目标是否落在该有序区间内。若在，则递归搜索该半；否则搜索另一半。

LeetCode 33 —— 搜索旋转排序数组#

一个升序数组在未知位置旋转。给定 target，返回其下标；不存在则返回 -1。要求 O(log n) 时间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            m = l + (r - l) // 2
            if nums[m] == target:
                return m
            if nums[l] <= nums[m]:
                # 左半 [l..m] 有序
                if nums[l] <= target < nums[m]:
                    r = m - 1
                else:
                    l = m + 1
            else:
                # 右半 [m..r] 有序
                if nums[m] < target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1
        return -1

此处有个细节：nums[l] <= nums[m] 使用了 <=。当 l == m 时，左半部分仅含单个元素 nums[l]，显然有序，<= 正好覆盖此情况。

六、寻找峰值：在无序数组上二分#

峰值定义为严格大于左右邻居的元素。尽管数组无序，但只要利用斜率方向这一局部单调性，仍可高效找到峰值。

LeetCode 162 —— 寻找峰值#

峰值元素严格大于其相邻元素。给定整数数组 nums（约定 nums[-1] = nums[n] = -∞），返回任意一个峰值的下标。要求 O(log n) 时间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            m = l + (r - l) // 2
            if nums[m] < nums[m + 1]:
                l = m + 1        # m 在上升段，峰一定在右边
            else:
                r = m            # m 在下降段或就是峰，往左搜（含 m）
        return l

逻辑如下：

若 nums[m] < nums[m + 1]，说明正在上升；由于 nums[n] = -∞，右侧必存在峰值，故舍弃左半。
若 nums[m] >= nums[m + 1]，说明正在下降或已达峰顶；由于 nums[-1] = -∞，左侧（含 m）必存在峰值，故舍弃右半。

每次迭代都将区间减半，同时保证“当前区间内至少存在一个峰值”这一不变量成立。

这类问题是“在无序数组上利用局部单调性进行二分”的典范。一旦识别出这种性质，模板应用便水到渠成。

七、答案空间二分：直接扔掉数组#

二分查找最强大的推广是完全脱离数组，直接在答案的可能取值范围内搜索。只要能设计一个判定函数 feasible(x)，就能快速定位最优解。

该模式适用于满足以下三个条件的问题：

答案是某个整数（或实数），且其范围 $$[lo, hi]$$ 已知。
存在一个函数 feasible(x)，可判断 x 是否为有效解。
feasible 具有单调性：存在阈值 $$x^*$$ ，使得 feasible(x) 在 $$x^*$$ 一侧全为 False，另一侧全为 True。

此时，二分查找可在 $\log(hi - lo)$ 次迭代内找到 $$x^*$$ ，每次仅需一次 feasible 调用。上图展示了“在 D 天内运送包裹”问题：上半部分是“所需天数 vs 载重”的单调递减阶梯函数，下半部分演示了区间 [l, r] 如何收缩至最优解。

LeetCode 1011 —— 在 D 天内送达包裹的能力#

必须按顺序在 D 天内运完 weights 中的所有包裹，每天载重固定。求满足条件的最小载重。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def shipWithinDays(self, weights: list[int], D: int) -> int:
        def feasible(cap: int) -> bool:
            days, cur = 1, 0
            for w in weights:
                if cur + w > cap:
                    days += 1
                    cur = w
                    if days > D:
                        return False
                else:
                    cur += w
            return True

        l, r = max(weights), sum(weights)
        while l < r:
            m = l + (r - l) // 2
            if feasible(m):
                r = m
            else:
                l = m + 1
        return l

三个关键设计点：

下界 max(weights)：载重低于最重包裹则无法运输。
上界 sum(weights)：一天运完所有包裹显然可行。
单调性：若载重 c 可行，则任何 c' > c 也可行（运力更强只会更快完成）。因此可行解集为 $[x^*, +\infty)$ ，使用左边界模板即可找到 $$x^*$$ 。

LeetCode 875 —— 爱吃香蕉的珂珂#

珂珂每小时以速度 k 吃一堆香蕉（每小时最多吃一堆）。求在 h 小时内吃完所有香蕉的最小速度 k。

套路相同，仅判定函数不同：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        def feasible(k: int) -> bool:
            hours = sum((p + k - 1) // k for p in piles)
            return hours <= h

        l, r = 1, max(piles)
        while l < r:
            m = l + (r - l) // 2
            if feasible(m):
                r = m
            else:
                l = m + 1
        return l

一旦掌握一道，其余皆可复用。LeetCode 410（分割数组的最大值）、1482（制作 m 束花的最少天数）、719（第 K 小的距离对）等题均属此类，核心工作仅在于设计 feasible 函数。

八、四种常见 bug，按出错频率排序#

写二分时常见的错误基本只有以下四种。

区间与更新方式不匹配：l < r 配 r = m - 1，或 l <= r 配 r = m。牢记：闭区间用 <= 和 m ± 1，半开区间用 < 和 m。其他组合必然出错。

返回值错误：基础模板返回 m 或 -1；左边界返回 l；右边界返回 l - 1——漏掉 -1 是经典错误。无论哪种模板，返回前都应验证：0 <= idx < len(nums) and nums[idx] == target。

mid 取整忘记 +1：若更新写成 l = m（而非 l = m + 1），需改用上中位数：m = l + (r - l + 1) // 2。否则当 r = l + 1 时，m = l，l = m 导致无进展，陷入死循环。LeetCode 69（sqrt）是典型例子。

(l + r) // 2 整数溢出：Python 无此问题，但在 C++/Java 中，当 l, r 接近 $2^{31}$ 时会溢出。养成写 l + (r - l) // 2 的习惯，零成本却能避免跨语言陷阱。

简单调试方法：在循环内添加 print(f"l={l} r={r} m={m} nums[m]={nums[m]}")，验证三点：(a) 区间每轮缩小，(b) 不变量“答案在 [l, r] 内”始终成立，(c) 返回下标对应的值符合预期。

九、如何选择合适的模板#

大部分问题可归为以下几类：

只需任一匹配下标，重复元素无关紧要：用基础模板（闭区间 [l, r]）。
找第一个匹配、插入位置或最小可行值：用左边界模板。
找最后一个匹配或最大可行值：用右边界模板。
判定条件为黑盒（版本、容量、速度等）：直接在答案空间上使用左边界模板，忽略数组。
数组无序但局部单调（如峰值、旋转数组）：仍用基础模板，但比较逻辑需改为检查结构性质（如哪半有序、斜率方向），而非直接与目标比较。

若不确定，推荐优先使用半开区间 [l, r)：它能自然处理“插入末尾”的情况，切换到浮点数时无需修改，且 l < r 的终止条件更直观。

十、二分查找在工程中的实际应用#

二分查找远不止是面试技巧，它是真正支撑现代基础设施的核心算法之一。

数据库索引（B 树、B+ 树、LSM-tree 的有序段）本质上是高分支因子的多路二分查找。在十亿行表上执行 WHERE id = 12345，核心操作仅需约 $\log_B n \approx 4$ 次磁盘读取（ $$B$$ 为页扇出）。没有二分查找，OLTP 数据库将无法高效运行。

git bisect 是二分思想在版本控制中的经典应用：标记一个 commit 为 good，另一个为 bad，自动检出中间 commit 测试，并递归缩小范围。千次 commit 的回归问题，最多十次测试即可定位。

标准库函数也体现了这些模板：Python 的 bisect_left/bisect_right、C++ 的 lower_bound/upper_bound、Java 的 Arrays.binarySearch，其命名直接对应本文内容——“lower bound”即左边界，“upper bound”即右边界减一。

学习率搜索、超参数调优、限流阈值探测等场景中，只要判定条件“单次验证昂贵但单调”，工业系统就会采用答案空间二分。例如，“99% 成功率下系统能承受的最大 QPS”这类问题，与“珂珂吃香蕉”本质相同，使用同一套逻辑。

十一、随手翻的小抄#

面试前一晚快速回顾：

 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
29
30
31
32
33
34
35
36
# 基础：找任意一个等于 target 的下标，找不到返回 -1
def std(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        m = l + (r - l) // 2
        if nums[m] == target: return m
        if nums[m] < target:  l = m + 1
        else:                  r = m - 1
    return -1

# 左边界：最小的 i 满足 nums[i] >= target
def lb(nums, target):
    l, r = 0, len(nums)
    while l < r:
        m = l + (r - l) // 2
        if nums[m] < target: l = m + 1
        else:                 r = m
    return l

# 右边界：最大的 i 满足 nums[i] <= target（不存在返回 -1）
def rb(nums, target):
    l, r = 0, len(nums)
    while l < r:
        m = l + (r - l) // 2
        if nums[m] <= target: l = m + 1
        else:                  r = m
    return l - 1

# 答案空间：[lo, hi] 内最小的 x 满足 feasible(x) == True
def search_answer(lo, hi, feasible):
    l, r = lo, hi
    while l < r:
        m = l + (r - l) // 2
        if feasible(m): r = m
        else:            l = m + 1
    return l

建议练到形成肌肉记忆的题目：704（基础）、35（左边界）、34（左右边界）、278（黑盒判定）、33（旋转数组）、162（峰值）、1011（答案空间）、875（答案空间）。若每道都能在五分钟内从零写出，二分查找将再也不会成为你的障碍。

LeetCode（五）：二分查找

一、心智模型：维护一个不断缩小的区间#

二、基础模板：闭区间 `[l, r]`#

LeetCode 704 —— 二分查找#

三、边界模板：找第一个或最后一个位置#

左边界：找到第一个 `nums[i] >= target` 的位置#

右边界：找到最后一个 `nums[i] <= target` 的位置#

LeetCode 35 —— 搜索插入位置#

LeetCode 34 —— 在排序数组中查找元素的第一个和最后一个位置#

LeetCode 278 —— 第一个错误的版本#

四、两种区间约定，选一种用到底#

五、旋转数组：还能不能二分？#

LeetCode 33 —— 搜索旋转排序数组#

六、寻找峰值：在无序数组上二分#

LeetCode 162 —— 寻找峰值#

七、答案空间二分：直接扔掉数组#

LeetCode 1011 —— 在 D 天内送达包裹的能力#

LeetCode 875 —— 爱吃香蕉的珂珂#

八、四种常见 bug，按出错频率排序#

九、如何选择合适的模板#

十、二分查找在工程中的实际应用#

十一、随手翻的小抄#

LeetCode 算法模式 10 篇

读有所得？

一、心智模型：维护一个不断缩小的区间#

二、基础模板：闭区间 [l, r]#

LeetCode 704 —— 二分查找#

三、边界模板：找第一个或最后一个位置#

左边界：找到第一个 nums[i] >= target 的位置#

右边界：找到最后一个 nums[i] <= target 的位置#

LeetCode 35 —— 搜索插入位置#

LeetCode 34 —— 在排序数组中查找元素的第一个和最后一个位置#

LeetCode 278 —— 第一个错误的版本#

四、两种区间约定，选一种用到底#

五、旋转数组：还能不能二分？#

LeetCode 33 —— 搜索旋转排序数组#

六、寻找峰值：在无序数组上二分#

LeetCode 162 —— 寻找峰值#

七、答案空间二分：直接扔掉数组#

LeetCode 1011 —— 在 D 天内送达包裹的能力#

LeetCode 875 —— 爱吃香蕉的珂珂#

八、四种常见 bug，按出错频率排序#

九、如何选择合适的模板#

十、二分查找在工程中的实际应用#

十一、随手翻的小抄#

LeetCode 算法模式 10 篇

读有所得？

二、基础模板：闭区间 `[l, r]`#

左边界：找到第一个 `nums[i] >= target` 的位置#

右边界：找到最后一个 `nums[i] <= target` 的位置#