二分查找｜LeetCode 第一轮复盘

章节状态：第一轮已完成 7/7。标准二分与基础边界题已经稳定；需要延迟重做的重点题为 69、34、153、162。

一、题目清单

顺序	LeetCode	难度	题目	核心训练	第一轮情况
1	704	简单	Binary Search	标准二分、精确目标	一遍通过
2	35	简单	Search Insert Position	插入位置、返回边界	一遍通过
3	69	简单	Sqrt(x)	答案空间二分、边界推进	重点复盘
4	367	简单	Valid Perfect Square	整数边界、精确判定	一遍通过
5	34	中等	Find First and Last Position	左右边界二分	重点复盘
6	153	中等	Find Minimum in Rotated Sorted Array	旋转结构、全局排除证明	重点复盘
7	162	中等	Find Peak Element	局部趋势、存在性证明	重点复盘

二、当前掌握情况

标准二分的代码框架、基本边界处理以及对有序搜索空间的识别已经建立。704、35、367 等题能够一遍通过，说明目前的主要问题不是“不会写二分”，而是面对变体时，能否严格证明某个判断足以排除一半区间。

现阶段最需要巩固的迁移类型是：

• 答案空间二分： 69 Sqrt(x)
• 边界二分： 34 Search Range
• 依据数组结构排除区间： 153 Find Minimum
• 依据答案存在性排除区间： 162 Find Peak Element

这些题中出现的问题集中在同一根源：能够提出合理的局部判断，但需要进一步证明该判断是否足以支持全局区间排除。

三、二分查找的核心原则

1. 二分的本质是安全地排除一半

二分不只适用于“整个数组有序”的情况。更准确的适用条件是：搜索空间中存在某种单调结构、分界结构或存在性结论，使我们能够根据一次判断证明某一半不包含所需答案。

写下判断条件后，应立即追问：

这个条件能否证明被排除的整个区间都不包含答案？

153 中，nums[mid] < nums[mid + 1] 只是局部递增，不能确定唯一的全局最小值位于哪一侧；162 中，同样的局部上升却能保证右侧至少存在一个峰值。判断式是否充分，取决于题目要求的是唯一特定答案，还是任意一个满足条件的答案。

2. 先定义搜索目标

二分题常见目标包括：

• 精确找到 target；
• 找到第一个满足条件的位置；
• 找到最后一个满足条件的位置；
• 找到最大的合法答案；
• 保留任意一个可接受答案。

目标不同，判断条件、边界更新及最终返回值都会变化。不能只根据题目出现“有序数组”就直接套用标准模板。

3. 先定义区间含义，再选择循环条件

区间含义	循环条件	典型更新	终止状态
[left, right] 是尚未检查的区域	left <= right	left = mid + 1 或 right = mid - 1	left > right，区域为空
[left, right] 始终包含答案	left < right	一侧排除 mid，另一侧保留 mid	left == right，只剩答案

标准 target 搜索和 Search Range 的边界搜索通常属于第一种模型；153、162 属于第二种模型。

不要简化成“查 target 用 <=，其他题用 <”。真正应该判断的是：

检查 mid 后，是否一定排除 mid？

4. 每次更新必须保证区间严格缩小

普通偏左中点：

mid = (left + right) // 2

当区间为 [2, 3] 时，mid == 2。因此：

left = mid

不会缩小区间，可能导致死循环。若必须保留 mid 并更新左边界，应使用偏右中点：

mid = (left + right + 1) // 2

实用对应关系：

right = mid  → 通常使用普通偏左中点
left = mid   → 通常使用偏右中点

每次写完边界更新，都用 [2, 3] 和 [2, 2] 代入，检查区间是否继续推进以及访问是否越界。

5. 区分索引、索引处的值和题目要求的返回值

mid        是索引
nums[mid]  是该索引对应的值
left/right 通常是搜索边界索引
target     是目标值

34 中必须比较 nums[mid] 与 target，不能比较 mid 与 target。返回内容同样要服从题意：153 返回最小元素的值，所以返回 nums[left]；162 返回峰值索引，所以返回 left。

6. 循环结束后必须解释边界语义

不要把 return left 或 return right 当成固定结尾。必须从循环不变量和终止状态推导答案：

• left > right：未检查区域为空，答案可能由提前返回、记录变量或分界位置表示；
• left == right：如果循环始终保证区间包含答案，那么唯一剩余位置就是答案；
• 边界搜索结束：left、right 往往分别停在真假区域的分界两侧。

四、重点题复盘

69. Sqrt(x)

题目目标

给定非负整数 x，返回算术平方根向下取整后的整数。可以把整数答案作为有序搜索空间，并定义：

n² <= x  → 合法
n² > x   → 不合法

本题要求寻找最大的合法整数，即“最后一个合法值”。

原始问题

原思路使用：

while left <= right:
    mid = (left + right) // 2

    if mid * mid < x:
        left = mid

将 mid 保留为候选答案的想法合理，但普通中点可能等于 left。例如 [2, 3] 中 mid == 2，执行 left = mid 后区间不变；[2, 2] 中更会无限重复。

另外，right = x // 2 会遗漏 x == 1。

与原始直觉一致的写法

class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x

        while left < right:
            mid = (left + right + 1) // 2

            if mid * mid <= x:
                left = mid
            else:
                right = mid - 1

        return left

循环不变量：[left, right] 始终包含最终答案。使用偏右中点后，left = mid 仍然能够保证区间缩小。

记录候选后排除 mid 的写法

class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x
        answer = 0

        while left <= right:
            mid = (left + right) // 2

            if mid * mid <= x:
                answer = mid
                left = mid + 1
            else:
                right = mid - 1

        return answer

left = mid + 1 不表示 mid 不是答案；answer 已经保存了它，算法只是继续寻找更大的合法值。

34. Find First and Last Position of Element in Sorted Array

正确建模

分别寻找：

左端点 = 第一个 nums[i] >= target 的位置
右端点 = 第一个 nums[i] > target 的位置 - 1

第一轮出现的问题

1. 比较了索引 mid 与 target，而不是 nums[mid] 与 target。
2. first_greater 返回第一个严格大于 target 的位置，最终右端点必须减一。
3. 在确认索引合法之前访问 nums[left_bound]，空数组或 target 大于全部元素时会触发 IndexError。
4. 使用整数结果覆盖内部函数名，降低可读性；grater 还应拼写为 greater。

正确写法

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def first_equal_or_greater(target: int) -> int:
            left, right = 0, len(nums) - 1

            while left <= right:
                mid = (left + right) // 2

                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1

            return left

        def first_greater(target: int) -> int:
            left, right = 0, len(nums) - 1

            while left <= right:
                mid = (left + right) // 2

                if nums[mid] <= target:
                    left = mid + 1
                else:
                    right = mid - 1

            return left

        left_bound = first_equal_or_greater(target)

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

        right_bound = first_greater(target) - 1
        return [left_bound, right_bound]

对 [5, 7, 7, 8, 8, 10] 和 target = 8，第一个函数返回 3，第二个函数返回 5，因此结果为 [3, 5 - 1] = [3, 4]。

153. Find Minimum in Rotated Sorted Array

旋转数组结构

无重复元素的旋转升序数组可以看作：

较大值升序段 + 较小值升序段
[4, 5, 6, 7] + [0, 1, 2]

第一轮的根本问题

nums[mid] < nums[mid + 1] 这个比较结果没有错；错误的是从局部递增推出“最小值一定在左侧”。mid 与 mid + 1 可能共同位于任意一个升序段，所以局部关系不足以判断旋转断点位于哪边。

另外还存在两个实现问题：mid + 1 可能越界；return left 返回索引，而题目要求返回最小元素的值。

为什么比较 nums[mid] 与 nums[right]

nums[mid] > nums[right]
→ mid 位于较大值段，断点在 mid 右侧
→ 最小值在 [mid + 1, right]

nums[mid] < nums[right]
→ [mid, right] 有序，其中最小的是 nums[mid]
→ 全局最小值在 [left, mid]

正确写法

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1

        while left < right:
            mid = (left + right) // 2

            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid

        return nums[left]

循环不变量：最小值的索引始终存在于 [left, right]。另一个分支必须写 right = mid，因为 mid 可能就是最小值。

162. Find Peak Element

为什么 nums[mid + 1] 不越界

循环使用：

while left < right:

普通中点向下取整，因此进入循环时必然有：

mid < right
mid + 1 <= right <= len(nums) - 1

所以 nums[mid + 1] 一定合法。left == right 时循环已经停止，不会再次访问右侧元素。

为什么局部趋势足够

如果：

nums[mid] < nums[mid + 1]

当前位置处于上坡。向右继续，要么在某处由上升转为下降并形成峰值，要么一直上升到最右端，而最右端相对于数组外侧的负无穷也是峰值。因此右侧至少存在一个峰值，可以执行 left = mid + 1。

否则当前位置处于下坡，左侧（包括 mid）至少存在一个峰值；mid 本身可能是峰值，所以执行 right = mid。

正确写法

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1

        while left < right:
            mid = (left + right) // 2

            if nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid

        return left

153 与 162 的关键差异：153 必须保留唯一的全局最小值，局部趋势不足以定位它；162 允许返回任意峰值，只要局部趋势能证明某一侧至少存在一个峰值，就可以放弃另一侧。

五、写二分代码前的检查清单

1. 搜索空间是数组索引、数值答案，还是某个可行范围？
2. 要找的是精确目标、第一个合法值、最后一个合法值，还是任意满足条件的位置？
3. 判断条件是否具有足够的全局信息，能证明被排除的一半不含所需答案？
4. [left, right] 表示尚未检查区域，还是一定包含答案的候选区间？
5. 每个分支中，mid 是被排除，还是可能为答案而必须保留？
6. 把 [2, 3] 和 [2, 2] 代入后，边界是否严格推进？mid + 1 是否仍在界内？
7. 循环结束时是 left > right 还是 left == right？这如何推出最终返回值？
8. 返回的是索引还是元素值？
9. 空数组、单元素、目标不存在、答案位于两端时是否安全？

六、复杂度

上述题目每轮都排除约一半搜索空间，典型时间复杂度为 O(log n)；若搜索的是数值答案区间 [0, x]，可写为 O(log x)。只使用常数个边界与中点变量时，额外空间复杂度为 O(1)。

七、延迟重做计划

在完成第一轮后的 3～7 天内，从空白重做：

69、34、153、162

每道题除通过测试外，还应能回答：

• 搜索空间是什么？
• 循环不变量是什么？
• 为什么判断条件足以排除这一半？
• 为什么不会死循环或越界？
• 循环结束后为什么返回该索引或该值？

如果四题均能独立完成并解释上述问题，可以将本章标记为“稳定掌握”；如果只能重现代码但无法解释区间含义，应继续保留在复习队列中。