📑 本页目录（点开跳转）
04 · 二分、排序与堆：怎样少看一半
⏱ 8 分钟 ｜ 边界二分、旋转数组最小值、最小的 k 个数
🎯 一句话
二分不是“猜中间数”，而是每一轮都能确定：答案还在左半还是右半。
🧩 题 1：升序数组中数字出现的次数
不要一个个数。找第一次出现的位置，再找第一次“大于目标”的位置；两者相减就是次数。
def lower_bound(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
def count_target(nums, target):
return lower_bound(nums, target + 1) - lower_bound(nums, target)
assert count_target([1, 2, 2, 2, 3, 4], 2) == 3
assert count_target([1, 2, 3], 9) == 0
不变量：答案永远在半开区间 [left, right) 中；right 不是最后一个合法下标，而是“答案可能到这里为止”的边界。
🧩 题 2：旋转数组的最小数字
[3, 4, 5, 1, 2] 看起来乱了，但中点总能和右端比较：中点更大，最小值在右边；中点更小，最小值在左边或就是中点。
def min_in_rotated(nums):
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]
assert min_in_rotated([3, 4, 5, 1, 2]) == 1
assert min_in_rotated([1, 2, 3]) == 1
🧩 题 3：最小的 k 个数
当你只要前 k 个，不必把全部排好。Python 的最小堆直接拿前 k 个最小元素。
import heapq
def smallest_k(nums, k):
if not 0 <= k <= len(nums):
raise ValueError("k out of range")
return heapq.nsmallest(k, nums)
assert smallest_k([4, 5, 1, 6, 2, 7, 3, 8], 4) == [1, 2, 3, 4]
⚠️ 面试若要求手写，可用“大小为 k 的最大堆”；但先把“只维护 k 个候选”这个思想弄懂。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 不靠数据的 AI 07 · 启发式与 A* | ⭐ 题 3 的 heapq 换个场景就是 A* 的心脏：按 $f = g + h$ 最小取出下一个节点，用的就是同一个最小堆 |
🛑 可以停在这里
二分每轮都删掉一半，前提是你说得出删掉那一半为什么不可能有答案。
✅ 检查点
为什么 lower_bound 的右边界写成 len(nums) 而不是 len(nums)-1？
👀 看答案
因为要表达“目标比所有元素都大”时的插入位置；半开区间也让空数组和边界判断统一。
⚡ 走神救援
- 二分找的是边界，不只是值。
- 旋转数组用
mid和右端比较，确认最小值在哪半边。 - 只要前 k 个：维护 k 个候选，不要先全排序。