题目

在有 个元素的升序数组 中查找关键字 。查找算法的伪代码如下所示。

k = 0;
while (k < n 且 A[k] < x) k = k + 3;
if (k < n 且 A[k] == x) 查找成功；
else if (k - 1 < n 且 A[k - 1] == x) 查找成功；
else if (k - 2 < n 且 A[k - 2] == x) 查找成功；
else 查找失败；

本算法与折半查找算法相比，有可能具有更少比较次数的情形是( )。

错因

A

误以为"找不到 = 比较次数少"。其实当 不在数组中且 比所有元素都大时，循环必须一直跳到 才退出，跳跃次数约为 ；即使 在数组范围内但不存在，循环也要走到 处才能停，平均也要跳 次左右。这都远多于折半查找在失败时的 次比较（）。"找不到"对跳跃查找毫无帮助。

C

把"接近结尾"和"接近开头"看成对称——其实两端完全不对称。本算法是单向跳跃（ 从 0 出发只增不减）， 在结尾意味着 要跳到接近 才退出循环，跳跃次数约 ，比折半的 多得多。折半查找在结尾命中的比较次数约 ，几乎与位置无关；而跳跃查找在结尾时比较次数最大。

D

误以为"中间位置 = 折半查找最快 = 跳跃查找也快"。其实折半查找在中间命中只需 1 次（第一次比较就命中根中点），跳跃查找在中间需要 次跳跃才到达 的位置。两者一对比，跳跃查找在中间反而最吃亏——折半查找在中间是它的最优情形。

总解析

先看清算法在做什么：

k = 0;
while (k < n 且 A[k] < x) k = k + 3;

每次让 加 3，跳过 3 个位置——这是一个步长为 3 的顺序跳跃查找。退出循环后 （或 ），再通过 A[k-2], A[k-1], A[k] 三个相邻位置回查命中点。

比较次数估计（与 的位置 相关）：

• 跳出 while 循环约需 次跳跃，每次循环至少 1 次比较。
• 之后最多 3 次回查比较。

总比较次数 ，线性正比于 的位置。

对比折半查找：

• 总比较次数 ，对 大约是 10 次左右，与位置基本无关。
• 中间命中最快（1 次比较），最深的叶子也只要 10 次。

两种算法在不同场景下的比较次数对照：

场景	跳跃查找比较次数	折半查找比较次数
位置 （开头附近）	次	次
位置 （中间）	次	次（中点命中最快）
位置 （结尾附近）	次	次
不在数组中	到 次	次

只有当 位置非常靠前时（例如 左右），跳跃查找的 才会少于折半的 。

直观理解：跳跃查找擅长"开头瞬命中"，因为 从 0 出发，前几跳就能找到接近开头的目标；任何一个"远离开头"的目标都让它越来越慢。折半查找则对位置不敏感——无论目标在哪里，比较次数都被 牢牢压住。

最终答案是 B（当 接近数组开头处）。