LeetCode（五）—— 二分查找

二分查找是一种"看着简单、写起来翻车"的算法。思路一句话能讲完——每次把搜索区间砍掉一半——但真要在面试中一气呵成写对、还要分得清"找第一个"和"找任意一个"，就会发现各种边界条件让人抓狂。本文不打算再罗列一遍模板，而是想说清楚一件事：为什么模板长这样。一旦理解了背后的不变量，< 还是 <=、right = mid 还是 right = mid - 1，就不再是需要硬背的细节，而是机械推导出来的结论。

一、心智模型：维护一个收缩的区间

二分查找本质上是一个区间收缩问题。我们用两个指针 l、r 框出"还有可能藏着答案"的那段数组，每轮选中点 m，看一眼 nums[m]，然后据此把区间砍掉一半。上图展示了典型情景：长度 16 的有序数组，查找 23，四步窗口从 16 收缩到 1。

整套算法就靠一条不变量撑着：

不变量：在每一轮迭代开始时，如果答案存在，它一定落在当前的 [l, r]（或 [l, r)）里。

只要这条不变量始终成立，算法就是对的。一旦哪一步把答案踢出了区间——比如在"找第一个等于 target"时遇到 nums[m] == target 就直接 r = m - 1——后面的搜索就全是无效操作。

为什么二分是 $O(\log n)$？$k$ 轮过后窗口里最多剩 $\lceil n / 2^k \rceil$ 个元素，要让它收缩到 1，就需要 $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 超过 INT_MAX 时不会溢出。Python 用大整数所以无所谓，但这个习惯换到 C++/Java 上立刻救命。

LeetCode 704 · 二分查找

 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，循环根本不会进入；单元素时 l == r == 0，l <= r 成立一次，要么命中要么走出循环返回 -1。

三、边界模板：第一个 / 最后一个

很多题目并不只问"存不存在"，而是要"第一个满足条件的位置"或"最后一个满足条件的位置"，乃至插入位置。基础模板搞不定，因为 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 可能是答案，留在 [l, r) 里
    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 才是最后一个 <=target 的位置。同样要做 l - 1 >= 0 and nums[l - 1] == target 的合法性检查。

LeetCode 35 · 搜索插入位置

这一题就是左边界模板，零修改：

 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 · 在排序数组中查找元素的第一个和最后一个位置

两个模板都用上，再做一次合法性检查：

 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 · 第一个错误的版本

同样是左边界模板，但"数组"变成了一个黑盒判定函数 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)。两种都对，但在同一个函数里混用就会无限循环。

上图把两套约定并排放，每一步下面用方括号标出当前区间。配对规则是机械的：

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

每个函数选定一种约定，全程贯彻。新手最常见、也最致命的 bug 是 l < r 配 r = m - 1：区间收缩到 [l, l] 时 m = l，再 r = l - 1 退出循环——看似正常，实际上可能跳过了答案。反过来更糟：l <= r 配 r = m，当 l == r == m 时 r = m 维持不变，无限循环卡死。

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

到目前为止我们的数组都是有序的。旋转数组虽然整体无序，但有一个好用的结构性质：从任意一个位置切开，至少有一半是有序的。这就够了。

上图跟踪 nums = [4, 5, 6, 7, 0, 1, 2] 找 0 的过程。每一步都先判定哪半边是有序的（比较 nums[l] 和 nums[m]），再看 target 是否落在那个有序区间里：在就往里搜，不在就往另一半搜。

LeetCode 33 · 搜索旋转排序数组

 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 · 寻找峰值

 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）
        return l

如果 nums[m] < nums[m + 1]，说明此处在上升；按约定 nums[n] = -inf，往右走早晚会下降，所以右半边一定有峰。如果 nums[m] >= nums[m + 1]，要么自己就是峰，要么在下降，结合 nums[-1] = -inf，左半边（含 m）一定有峰。两种情况都能砍掉一半，并且不变量"区间内至少存在一个峰"始终成立。

这道题是"在无序数组上利用局部单调性二分"的范式。一旦看出局部单调性的论证，模板照搬即可。

七、答案空间二分：把数组扔掉

二分查找最强大的扩展，是根本不在数组里搜，而在"答案的可能取值范围"里搜——只要我们能写出一个判定函数。

适用场景三个条件：

答案是一个整数（或实数），落在已知范围 $[lo, hi]$ 内。
存在判定函数 feasible(x)，能告诉我们 x 是否合法。
feasible 单调：存在一个阈值 $x^*$，使得 feasible(x) 在它一侧全为 False、另一侧全为 True。

二分就能在 $\log(hi - lo)$ 次内定位 $x^*$，每次只调用一次 feasible。上图就是"在 D 天内运送所有包裹"问题：上半张图画出"所需天数 vs 载重"的阶梯函数（单调递减），下半张图展示二分区间 [l, r] 一步步向答案收缩的过程。

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

按顺序把 weights 在 D 天内全部运完，每天载重固定，求满足条件的最小载重。

 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 · 爱吃香蕉的珂珂

同一个套路，骨架几乎一行不改，只换判定函数：

 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 的习惯，零成本，但换语言写时立刻派上用场。

简单的 debug 配方：在循环里加一行 print(f"l={l} r={r} m={m} nums[m]={nums[m]}")，盯三件事：(a) 区间每轮都在收缩，(b) 不变量"答案在 [l, r] 内"始终成立，(c) 返回的下标处的值是预期值。

九、模板挑选指南

一个简短的决策树覆盖大多数情况：

找任意一个匹配下标，重复元素无关：基础模板，闭区间。
找第一个、找插入位置、找最小可行值：左边界模板。
找最后一个、找最大可行值：右边界模板。
判定函数是黑盒（版本号、载重、速度）：在答案空间上跑左边界模板，数组什么的根本不存在。
数组无序但局部单调（峰值、旋转数组）：基础模板照搬，只是比较逻辑改成检查结构性质（哪半有序、哪边在上升），而不是和 target 比大小。

拿不准的时候，优先用半开区间 [l, r)。它通用性更好——能自然表达"插到末尾之后"的情况，从整数换到浮点也不用改循环条件，l < r 更明确地表明终止时刻。

十、二分在工程里到底活在哪里

二分查找绝不只是面试题。它是少数几个真正在驱动现代基础设施的算法之一。

数据库索引——B 树、B+ 树、LSM-tree 的有序段——本质上是分支因子大于 2 的多路二分。在十亿行表上做 WHERE id = 12345，无非就是 $\log_B n \approx 4$ 次磁盘读，其中 $B$ 是页扇出。没有二分，OLTP 数据库就别想存在。

git bisect 是把二分用到了 commit 历史上：把一个 commit 标记为 good、一个稍后的标记为 bad，自动取中点 checkout 让你测，再据此递归。一千个 commit 找回归 bug，10 次测试搞定。

各种语言标准库里 bisect_left / bisect_right（Python）、lower_bound / upper_bound（C++）、Arrays.binarySearch（Java），就是第二、三节里的模板。命名很诚实：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（答案空间）。如果每道都能在五分钟内从零写出，二分查找就再也不会卡住你。