有序向量：插值查找
看完你能说清插值查找何时碾压折半、何时反而退化
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
有序向量：插值查找
看完你能说清插值查找何时碾压折半、何时反而退化
查字典的直觉
翻字典查 zebra，你不会从中间翻开——你知道 z 在后段，会直接翻到靠后的位置再微调。人脑天然就会按数值比例猜位置。插值查找，就是把这份直觉写成公式。
字典里字母靠后的直觉位置，对应按值占比估算的下标
折半 vs 插值的猜测策略
两者都只做一次猜测，但猜的位置不同——这直接决定了猜测次数的差异。
- 永远猜正中点 mi = (lo+hi)/2
- 只看区间长度，不看元素值
- 最坏 O(logn)，且稳定不波动
- 按目标值线性估计 mi（横纵比例换算）
- 利用有序性猜『应该在哪』
- 均匀分布时平均 O(loglogn)，分布偏斜退化
插值查找公式与实现
用 Python 实现插值查找：公式落成一行代码，循环逼近目标 e。
第 5 行把 mi = lo + (hi-lo)*(e-a[lo])/(a[hi]-a[lo]) 直接落地；用整除避免浮点，第 4 行防除零，第 10 行的等值判断决定收缩方向。
手算一轮插值
拿一组具体数字，手算一轮插值查找的猜测与比较。
完整查找过程
插值查找不是一轮就结束，而是反复收缩区间，直到命中或为空。
最好与最坏情况
前面手算发现，均匀分布的有序向量里，插值查找几乎一步到位。但真实数据未必均匀，猜测策略对分布的依赖，决定了它的最好与最坏表现相差悬殊。
页码分布均匀时按比例翻页很准，乱序时只能退回逐页翻
loglogn 是什么概念
横轴是数据规模 n，纵轴是猜测次数。三条曲线分开看：线性几乎竖直上涨，logn 增长缓慢，loglogn 几乎贴地。
自测：复杂度判断
插值查找在什么前提下，平均复杂度才能达到 O(log log n)？
字宽折半
前面说过，纯插值遇到坏分布会退化到 O(n)。那能不能两头都要？让插值猜得快，又保证最坏不塌——把两种步长混着用。
导航给捷径（插值），但每步都强制走一段保险车道（折半）
三种策略综合对比
折半与插值看似只差一个公式，实则依赖的前提完全不同，选错场景会从优雅跌到 O(n)。
- 复杂度稳定 O(logn)，无波动
- 只要求有序，对分布无任何假设
- 最坏也无害：数据倾斜时仍砍一半
- 均匀分布 O(loglogn)，倾斜退化 O(n)
- 隐含假设：元素近似均匀分布
- 最坏有害：不均匀时每轮可能只减一
要点收束
- ✓插值按数值比例猜位置，均匀分布时接近一次命中
- ✓秩估算公式本质是线性内插，前提是有序
- ✓最坏退化到 O(n)，如指数分布的数据
- ✓loglogn 增长极慢，百万级约只数次比较
- ✓实践中常用插值与折半混合，兼顾稳健与速度
课后思考
先自己想，再看参考答案——答案只是思考的起点。
参考答案想想手算过程：mi 由 hi-lo 按比例推算，均匀分布下猜测才准。分布严重偏斜时，比例估计失真，可能退化回 O(n)，等价于每次只排除一个元素。
参考答案重复值会让插值点集中在同一区域，区间收缩变慢，甚至可能越界。工程上通常先夹逼边界：命中后向两侧线性收缩，或改用带边界修正的版本保证进度。
参考答案凡是能对键做合理线性插值的场景都可用，如按时间戳查日志、浮点均匀采样。但分布未知、数据倾斜或键不可插值时，折半的稳定 O(logn) 更可靠——稳定压倒理论最优。