题22

题22

题目

【2016 统考真题】在有 个元素的升序数组 中查找关键字 .
查找算法的伪代码如下所示.

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. 当 不在数组中
B. 当 接近数组开头处
C. 当 接近数组结尾处
D. 当 位于数组中间位置

分析

一次跳 步，然后逐步回退，这个算法的时间复杂度是多少？这个算法的时间复杂度是 的，因为最坏情况下，需要遍历整个数组。
这个算法的优势在于，对于一些特定的情况，比如 接近数组开头处，可能会比折半查找更快，因为折半查找需要从中间开始查找，而这个算法可以从开头开始查找。

解

B
本题为送分题。
该程序采用跳跃式的顺序查找法查找升序数组中的 。显然, 越靠前,比较次数越少。