第6章｜二分、堆与优先队列

Unit 01 · LeetCode #704

← Unit 00
仅本次页面有效
704
Binary SearchArray · Search · Invariant

二分不是反复猜中点，
而是反复证明一整段不可能。

每轮比较都必须维护一个可信承诺：若目标存在，它仍位于当前闭区间中。只有当比较结果能够证明某一整段全部过小或全部过大时，才可以删除这一段。

检测到上次学习记录可以恢复阶段、二分状态、代码、迁移进度和滚动位置。
LeetCode #704 原题内容题面转述、前置概念与复杂度

题目要求

给定一个按严格递增顺序排列的整数数组 nums 和目标值 target。若目标存在，返回其下标；否则返回 -1。要求算法时间复杂度为 O(log n)。

class Solution: def search( self, nums: List[int], target: int ) -> int: pass

约束

  • 1 ≤ nums.length ≤ 10⁴；
  • 数组中的所有整数互不相同并按升序排列；
  • 若目标不存在，必须返回 -1。

示例

nums = [-1,0,3,5,9,12], target = 9
输出：4
nums = [-1,0,3,5,9,12], target = 2
输出：-1

本页主方法

闭区间迭代二分：初始化 left=0、right=n-1，循环条件为 left≤right。每轮排除至少一个位置，时间复杂度 O(log n)，额外空间 O(1)。

与 Unit 00 的联系：从概念地图进入第一个完整证明

Unit 00：候选压缩

识别候选空间、单调证据、区间契约与严格推进。

→
Unit 01：闭区间精确查找

把抽象概念落实为每一轮可验证的“比较—排除—保持不变量”。

候选闭区间

[left,right]中的每个位置仍可能是目标；区间外位置已被证明不可能。

中点 mid

当前区间内用于获取排除证据的位置，而不是一个“随机猜测”。

严格收缩

未命中时，新区间长度必须小于旧区间，否则循环可能永不终止。

对数复杂度

候选规模连续减半：n → n/2 → n/4 → … → 1，轮数约为 log₂n。

nums = [-1,0,3,5,9,12]target = 9
left=0
mid=2
right=5
target=9
本轮排除证据

比较nums[mid]与target，决定哪一整段可以安全删除。

当前闭区间契约 若target存在，则其下标位于[left,right]中。

区间演化记录

nums[mid]3
比较结果3 < 9
旧区间长度6
新区间长度—

核心不变量

若目标存在，它始终位于当前闭区间 [left,right] 内；区间外元素已被比较结果证明不可能。

更新判断

先判断mid是否命中；未命中时，再判断mid及其哪一侧可以整体排除。

剩余候选位置6
已完成比较0
本轮排除数量0
区间是否严格缩小—
当前结果未确定
线性扫描与二分搜索的信息利用方式

线性扫描每次通常只排除当前一个位置；二分比较利用升序关系，一次排除连续半段。

错误更新实验：使用 left = mid

在相邻区间中，向下取整的mid可能等于left。如果未命中后仍令left=mid，候选区间将完全不变。

闭区间二分的三段式正确性

代码正确不仅因为示例能运行，还因为初始化、每轮更新和退出条件共同维护同一个不变量。

初始化

目标若存在，初始时必在完整数组[0,n−1]中。

保持

根据升序和比较结果，只删除已证明不可能的一侧。

终止

每轮严格缩小；区间为空时，所有位置均已被排除。

补全LeetCode提交代码闭区间[left,right]
class Solution:
def search(self, nums, target) -> int:
left =
right =
while :
mid =
if nums[mid] == target:
return mid
if nums[mid] < target:
else:
return
层 1｜区间：闭区间从数组首尾开始，两个端点都属于候选。
层 2｜循环：只要 left ≤ right，区间仍至少包含一个位置。
层 3｜证据：nums[mid] 小于目标时，mid 与其左侧都已被证明过小。
层 4｜进度：未命中时必须排除 mid 本身，因此使用 mid+1 或 mid−1。
层 5｜退出：闭区间为空表示所有位置均已排除，返回 −1。
中点公式：Python中 (left+right)//2 不会发生整数溢出；使用 left+(right-left)//2 仍能更直接表达“从left走半个区间”。
代码—候选区间—排除证据联动示例target=9
1class Solution:
2 def search(self, nums, target):
3 left = 0
4 right = len(nums) - 1
6 while left <= right:
7 mid = left + (right-left)//2
9 if nums[mid] == target:
10 return mid
12 if nums[mid] < target:
13 left = mid + 1
15 right = mid - 1
17 return -1
播放后观察：6个候选先缩为3个，再在第二次比较命中下标4。
完成代码联动后进入 LeetCode #374 官方迁移只有主代码正确或完整播放轨迹后才会解锁；提示与初始化骨架不计完成。
迁移题：LeetCode #374《猜数字大小》

这不是重新背一份二分代码。你需要识别：数组消失以后，候选空间仍是闭区间；比较证据从 nums[mid] 改为外部接口 guess(mid)。

官方题意

系统在整数 1..n 中固定选择一个秘密数字 pick。每次调用 guess(num) 会返回：

  • -1：你的猜测过大，即 num > pick；
  • 1：你的猜测过小，即 num < pick；
  • 0：猜中。
# guess(num) is provided class Solution: def guessNumber(self, n: int) -> int: pass
打开 LeetCode 官方原题 ↗

官方示例与约束

n = 10, pick = 6 → 输出 6
n = 1, pick = 1 → 输出 1
n = 2, pick = 1 → 输出 1
  • 1 ≤ n ≤ 2³¹−1；
  • 1 ≤ pick ≤ n；
  • pick 在整个游戏中保持不变。
guess(mid) == -1 表示什么？
候选空间为什么从 [1,n] 开始？
两道读题检查都正确后，才能进入结构对照。
结构维度#704 二分查找#374 猜数字
候选对象数组下标 0..n−1整数值 1..n
获取证据读取 nums[mid]调用 guess(mid)
命中条件nums[mid] == targetguess(mid) == 0
目标更大nums[mid] < targetguess(mid) > 0
目标更小nums[mid] > targetguess(mid) < 0
按依赖顺序组装算法
点击上方步骤，将它们按算法依赖顺序排列。
槽位 1｜候选空间如何初始化整数闭区间？
槽位 2｜闭区间循环如何确保最后一个候选仍被检查？
槽位 3｜外部证据本轮比较结果从哪里获得？
槽位 4｜方向映射result > 0 时如何更新？
四个语义槽位全部正确后，才会显示组装结构。
left, right = 1, n while left <= right: mid = left + (right - left) // 2 result = guess(mid) # result == 0：返回 mid # result > 0：保留右半边 # result < 0：保留左半边

官方样例：n=10，pick=6

候选区间[1,10]
mid—
guess(mid)—
当前结论初始化
秘密数字始终位于当前闭区间中。
独立重写：不提供占位符或完整答案先运行完整样例
完整运行样例后，编辑器与检查按钮才会开放。
完成后停留在本页

不会自动跳转。可以继续重放失败与命中轨迹，或手动进入 Unit 02。

手动进入 Unit 02 →

第6章 Unit 01 Skill卡

闭区间二分的本质是维护候选集合：中点比较提供排除证据，更新式删除已经被证明不可能的位置，并确保区间严格缩小。你还把相同契约迁移到了没有数组的整数搜索空间。

题号与题型#704｜严格升序数组中的精确查找
触发信号数组有序，需要判断目标是否存在
候选空间闭区间[left,right]
核心不变量目标若存在，始终保留在候选闭区间
核心更新小于：left=mid+1；大于：right=mid−1
终止条件left>right表示候选区间为空
复杂度时间O(log n)，空间O(1)
常见错误left=mid导致死循环；区间语义与循环条件不一致
迁移能力#374：用 guess(mid) 替代 nums[mid]，闭区间证明不变