查找
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| linear search/ˈlɪnɪə sɜːtʃ/ | 线性查找 | xiàn xìng chá zhǎo |
| binary search/ˈbaɪnəri sɜːtʃ/ | 二分查找 | èr fēn chá zhǎo |
两种找法
- 线性查找 linear search 沿数组走：$O(n)$，无前置条件。二分查找 binary search 每次留下一半有序区间：比较中点、留一半——有序是前置条件，不是可选偏好。
{exercise:uni-cs0507-two}
练习
二分查找要求——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
无序数据上折半论证崩塌——静默给出错答案。
探测上界
- 每次探测砍掉一半候选：$k$ 次后至多剩 $\lceil n / 2^k \rceil$，最坏 $\lceil \log_2(n+1) \rceil$ 次探测——$n = 16$ 时是 $5$。
- 在有序数组 $[3, 7, \ldots, 63]$（16 格）上找 $43$：依次探测下标 $7, 11, 9, 10$——值 $31, 47, 39, 43$：四次探测，在 $10$ 号位找到。线性要走 $11$ 个值才到同一格。
{exercise:uni-cs0507-bound}
练习
16 格上二分查找最坏——次探测。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
log2 17 向上取整为 5：每次探测砍一半。
证明上界的落空查找
- 找 $64$（不存在，超出末端）：二分探测 $7 (31), 11 (47), 13 (55), 14 (59), 15 (63)$——五次探测后区间为空，报告不存在。线性为同一答案走满 $16$ 格。
- 经典陷阱：对无序数据二分会静默给出错答案；
lo = mid而非mid + 1死循环；定宽整型语言里用lo + (hi - lo) // 2算中点。
{exercise:uni-cs0507-miss}
练习
课程数组上找 43 依次探测——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
中点 7 读 31（向右）、11 读 47（向左）、9 读 39、10 命中。