从算法到人工智能 · 第 11 课：二分查找——每次砍一半
想象一个游戏：我心里想一个 1 到 100 之间的数，让你猜，我只能回答"大了""小了""对了"。你怎么猜最快？
绝大多数人第一次会从 1 开始：1？2？3？……最倒霉要猜 100 次。
聪明人这么猜：先猜 50。"大了"→ 说明在 1~49，"小了"→ 说明在 51~100。每次猜中间那个数，每猜一次，范围砍掉一半。100 个数，最多 7 次就锁定答案。
这个"每次砍一半"的策略，就是二分查找（binary search）——O(log n) 复杂度的头号明星。
一、二分查找是什么：在有序里"折半"
前提很关键：数据必须已经排好序。 二分查找做的事，是在一个有序数组里，快速找到目标值的位置。
思路就三步，反复做：
- 看中间那个元素；
- 比目标大 → 目标只可能在左半边；
- 比目标小 → 目标只可能在右半边；
- 每次都把范围砍一半，直到找到或范围空了。
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2 # 取中间下标
if nums[mid] == target:
return mid # 找到了
elif nums[mid] < target:
left = mid + 1 # 目标在右半边
else:
right = mid - 1 # 目标在左半边
return -1 # 没找到
nums = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(nums, 7)) # 3
print(binary_search(nums, 8)) # -1二、为什么是 O(log n)：砍半的威力
这是理解对数复杂度最好的例子。
一个长度 n 的数组，每次砍一半：
- 第 1 次后剩 n/2
- 第 2 次后剩 n/4
- 第 3 次后剩 n/8
- ……
- 第 k 次后剩 n/2^k
什么时候砍到只剩 1 个（或空）？当 n / 2^k ≈ 1，也就是 k ≈ log₂n。
所以二分查找最多只要 log₂n 步。
感受一下这有多恐怖：
| 数据量 n | 线性查找 O(n) | 二分查找 O(log n) |
|---|---|---|
| 100 | 100 次 | 约 7 次 |
| 1 万 | 1 万次 | 约 14 次 |
| 100 万 | 100 万次 | 约 20 次 |
| 10 亿 | 10 亿次 | 约 30 次 |
10 亿个数据，二分查找只要 30 步。 这就是"每次砍一半"的威力——数据翻倍，它只多花一步。
三、二分查找的两个经典"翻车点"
二分查找代码看着短，但极其容易写错。历史上无数程序员栽在两个细节上，面试也最爱问这两点：
坑 1：边界条件 left <= right 还是 left < right？
我用的是 left <= right，对应区间是闭区间 [left, right]——左右都算数。
为什么是 <=？因为当 left == right 时，区间里还有一个元素没检查，必须再进循环看一次。如果你用 <，就会漏掉这个元素。
坑 2：mid = (left + right) // 2 会溢出吗？
在 Python 里，整数任意大，永远不会溢出，所以这么写没问题。
但在 C、Java 这类语言里，left + right 可能超过整数上限溢出。所以老练的程序员写：
mid = left + (right - left) // 2 # 更安全的写法，先算差再除两个坑记牢：闭区间用 <=，算 mid 用 left + (right-left)//2。
四、Python 里的"开箱即用"：bisect 模块
实际写代码，你几乎不用手写二分查找——Python 自带 bisect 模块：
import bisect
nums = [1, 3, 5, 7, 9]
print(bisect.bisect_left(nums, 5)) # 2 找到第一个 >= 5 的位置
print(bisect.bisect_left(nums, 4)) # 2 4 不在，返回"应该插在哪"（保持有序）
print(bisect.bisect_right(nums, 5)) # 3 找到第一个 > 5 的位置
# 直接插入且保持有序
bisect.insort(nums, 4)
print(nums) # [1, 3, 4, 5, 7, 9]记忆：bisect_left 找"最左边能插的位置"（左边界），bisect_right 找"最右边能插的位置"（右边界）。查找"第一个等于 target"用 bisect_left。
五、二分查找的进阶：不只是"找一个数"
二分查找最厉害的地方，是它不只能查"等于"，还能查"第一个满足某条件的位置"。这是它真正的通用形态：
在单调数组里，找一个"临界点"：左边都不满足某条件，右边都满足。二分能 O(log n) 找到这个临界点。
应用 1：找第一个大于等于 target 的位置（lower_bound）
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 # 第一个 >= target 的位置
nums = [1, 3, 5, 7, 9]
print(lower_bound(nums, 5)) # 2
print(lower_bound(nums, 6)) # 3（6 不在，返回 7 的位置）注意这里 right = len(nums)（开区间），所以循环条件是 left < right。区间开闭一变，写法跟着变——这就是二分容易乱的根源，认准一种写法练熟即可。
应用 2：求平方根（在"答案区间"上二分）
不用 math.sqrt，手写一个求整数平方根的二分。精髓：不是在有数据的数组上二分，而是在"可能的答案"上二分。
def my_sqrt(x):
left, right = 0, x
while left <= right:
mid = (left + right) // 2
if mid * mid <= x < (mid + 1) * (mid + 1):
return mid
elif mid * mid > x:
right = mid - 1
else:
left = mid + 1
return left
print(my_sqrt(10)) # 3（3²=9 ≤ 10 < 4²=16）
print(my_sqrt(16)) # 4这个思路很重要：凡是"在一个单调区间里找满足某条件的临界值"，都能二分——哪怕那是个连续的数值范围，不是现成的数组。
应用 3：旋转数组找最小值（面试经典）
一个本来有序的数组，被"旋转"了一下（比如 [4,5,6,7,0,1,2]），找最小值。用二分"找转折点"：
def find_min(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]: # 转折点在右半
left = mid + 1
else: # 转折点在左半（含 mid）
right = mid
return nums[left]
print(find_min([4, 5, 6, 7, 0, 1, 2])) # 0体会：这里二分找的不是"某个值"，而是"单调性断掉的那个转折点"——这是二分思想最灵活的应用。
六、复杂度小结
| 操作 | 复杂度 |
|---|---|
| 线性查找 | O(n) |
| 二分查找 | O(log n) |
| 二分查找（递归版） | O(log n) 时间，O(log n) 栈空间 |
| 二分查找（迭代版） | O(log n) 时间，O(1) 空间 |
心法：二分查找的本质，是每一步排除掉一半的候选。凡是"能一眼判断目标在哪一半"的问题，都能二分。有序只是最典型的场景。
七、动手时间 🎯
实验 1：亲眼看看 log n 的威力
import time
def linear_search(nums, target):
for i, x in enumerate(nums):
if x == target:
return i
return -1
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
for n in [1000, 100000, 10000000]:
nums = list(range(n))
target = n - 1 # 最坏情况：找最后一个
start = time.time()
linear_search(nums, target)
t1 = time.time() - start
start = time.time()
binary_search(nums, target)
t2 = time.time() - start
print(f"n={n}: 线性 {round(t1,6)}s | 二分 {round(t2,6)}s")你会看到：数据一大，线性查找慢得肉眼可见，二分查找永远是"0.000…"。
实验 2：写一个递归版二分查找
def binary_search_rec(nums, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
return binary_search_rec(nums, target, mid + 1, right)
else:
return binary_search_rec(nums, target, left, mid - 1)
nums = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search_rec(nums, 13, 0, len(nums) - 1)) # 6实验 3：找"第一个错误的版本"（lower_bound 实战）
假设有 n 个版本，从某个版本开始往后全是坏的（前面全是好的）。用二分找第一个坏版本：
def first_bad_version(n, is_bad):
left, right = 1, n
while left < right:
mid = (left + right) // 2
if is_bad(mid):
right = mid # mid 坏，第一个坏在左半（含 mid）
else:
left = mid + 1 # mid 好，第一个坏在右半
return left
# 假设第 4 个版本开始坏
print(first_bad_version(10, lambda v: v >= 4)) # 4实验 4（挑战）：在旋转数组里找目标值
结合"旋转数组找最小"和普通二分，写出在旋转数组里找目标值的完整解法：
def search_rotated(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# 判断哪一半是有序的
if nums[left] <= nums[mid]: # 左半有序
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else: # 右半有序
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
nums = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(nums, 0)) # 4
print(search_rotated(nums, 3)) # -1八、小结
- 二分查找 = 每次砍一半——前提是有序，复杂度 O(log n)，10 亿数据只要 30 步。
- 两个坑记牢：闭区间用
left <= right，算 mid 用left + (right-left)//2防溢出。 - 二分不止查"等于"——凡是单调区间里找临界点（第一个满足条件的、平方根、旋转转折点）都能二分，这是它最值钱的用法。
先别急着往后翻，把"线性 vs 二分"的实验跑一遍，亲眼看看 O(n) 和 O(log n) 的差距，二分的手感就长在你脑子里了。