意义与机制
线性查找依次检查数值，二分查找则检查当前区间的中间值。根据目标值比中间值大还是小，利用已有的排序关系排除其中一侧。
每次比较后，都必须保持以下条件：如果目标值存在，它就位于剩余区间内。区间为空时，便可得出目标值不存在的结论。
关系与条件
候选人数大约随着 n/2ᵏ 减少，因此比较次数呈对数增长。对于模拟中的无重复列表，当 n ≥ 1 时，最大比较次数可以与 ⌊log₂n⌋ + 1 进行比较。
排序的成本必须与搜索成本分开考虑。当解决在包含重复值的列表中找到第一个和最后一个位置的问题时，必须调整停止条件。
观察实验中需要注意的事物
二分搜索在每次探测时，将候选范围减半。
排序后的整数列表没有重复元素。 两种方法使用相同的列表。
关键关系与符号
binary steps ≤ ⌊log₂n⌋ + 1
| 符号 | 含义 | 单位 |
|---|---|---|
| n | 数据项数量 | 个 |
| k | 比较次数与范围减少量 | 次 |
工作实例
二分搜索需要什么？
排序列表 · 二分搜索在每次查询时，将候选范围减半。
常见误解
- 仅对未排序的列表应用中间值比较规则，并不能得到正确的二分查找。