📄 一句话概括
找数据两条路：线性查找挨个问（O(n)，但不挑食——乱的不乱的都行）；二分查找每问一次砍一半（O(log n)，但前提是已排序）——一百万数据前者最多一百万次、后者二十次，差距全在【数据有没有提前排好】。
📝 本节和前面几节的关系
4-14 的账本在这一篇兑现：O(n) 对 O(log n) 的正面交锋。回收 3-17 的二叉搜索树（每层砍一半的同构思想）与数据库课 7-7 索引（【先排序再查】的数据库形态）。
一、线性查找：挨个问
def linear_search(arr, target):
for i, x in enumerate(arr): # 从头到尾挨个比
if x == target:
return i # 找到返回下标
return -1 # 没找到
print(linear_search([8, 3, 9, 1], 9)) # 2
性格：O(n) 最坏查完整表；不要求有序、链表也能用（顺序访问正合适，回收 3-15）；数据一百万就要问一百万次——简单但贵。
二、二分查找：每次砍一半
前提：已排序。玩法像【猜 1~100 的数字】：报中间、听【大了／小了】、范围立刻砍半：
def binary_search(arr, target): # arr 必须升序！
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2 # 中点
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1 # 目标在右半：左边界跳过中点
else:
hi = mid - 1 # 目标在左半：右边界退回中点前
return -1
arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7)) # 3
为什么是 log n：范围每轮除以 2，一百万个元素约 20 轮见分晓（log2(1000000)≈19.9，4-14 刚验过）。排序一次 O(n log n)，之后成千上万次查找各 O(log n)——查找频繁时这笔投资稳赚（数据库索引的全部经济学）。
三、三分天下：查找方案选型
| 方案 | 查找 | 前提 | 适用 |
|---|---|---|---|
| 线性查找 | O(n) | 无 | 小数据、链表、就查一两次 |
| 二分查找 | O(log n) | 必须有序 | 静态数据、频繁查找 |
| 哈希（3-13） | O(1) | 内存换速度、无序 | 键值查询、超大表 |
注意二分不占地：有序数组好二分但插删要搬家（3-15）；要【又频繁插删又快速查】就升级到平衡树（3-17）——三招是一族演进。
四、动手 Demo：步数现场对比
arr = list(range(0, 2_000_000, 2)) # 100 万个偶数（已有序）
target = 1_999_998
steps = 0
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
steps += 1
if arr[mid] == target:
break
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
print("二分命中，下标", mid, "，步数", steps) # 步数 20
print("线性要", len(arr), "步") # 1000000
看到什么算成功：二分命中，下标 999999 ，步数 20、线性要 1000000 步。
读结果：20 对 100 万——五万倍的差距来自【每次砍半】。这份账就是 4-14 大 O 表的第一行实录。
五、30 秒实验
Python 标准库自带二分：import bisect; bisect.bisect_left([1,3,5,7], 5) 得 2（应插入的位置）。不用手写循环、边界零操心——实战直接用它；手写版的意义在于搞懂【砍半】。
六、常见误区
- 【二分查找只要数组就行】——错。有序是生命线；乱序数组二分的结果毫无意义（它信任 arr[mid] < target 就能跳半边）。先 sort 再二分，或用平衡树。
- 【mid = (lo + hi) // 2 天经地义】——C／Java 里有暗雷：lo+hi 相加可能整数溢出（3-12！）成负数；标准写法
mid = lo + (hi - lo) // 2。Python 整数不溢出才没事。 - 【二分只能找【等于】】——窄了。bisect_left／right 能找【第一个大于等于 x 的位置】——范围查询、去重插入全靠它；二分是【在有序世界定位】，不只是【找某个值】。
自测三问（点开对答案）
1. **二分查找的前提与复杂度？** 答：数据必须有序；每轮砍半，O(log n)——一百万数据约 20 轮。 2. **查找频繁时为什么【先排序再二分】划算？** 答：排序一次 O(n log n)，之后每次查找 O(log n)；查 k 次总账 n log n + k log n——线性则是 k x n，k 大时天差地别。 3. **什么场景二分不如哈希？** 答：只按【键精确找】且数据动态变化时——哈希 O(1) 直达；二分要维持有序（插删搬家 O(n)），平衡树又重一层。- ☐ 下一节（4-16 广度优先查找、深度优先查找、剪枝）
相关笔记
- 时间复杂度与大 O —— 五万倍差距的记账本
- 树形结构 —— 同构的【砍半】思想
- 数据库 7-7 · 索引 —— 【先排序再查】的数据库版
- ⌨️ 编程原理 · 索引 —— 全课路线图