Question

对于长度为18的顺序存储的有序表,若采用折半查找,则查找第15个元素的比较次数

91.对于长度为18的顺序存储的有序表,若采用二分查找,则查找第15个元素的查找长度为（）.
A.2 B.3 C.4 D.6

Answer 1

C

（1+2*2+3*4+4*2）/9

一个有序的线性表，查找，先取中A[18/2]；再判断要查找的数与A[18/2]的谁大。

折半查找原码是：

if (key==r[mid]) return mid;

else if(key>r[mid]) low = mid+1;

else(key<r[mid]) high = mid-1;

扩展资料：

① 首先确定整个查找区间的中间位置mid=（ left + right ）/2 。

② 用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功若大于，则在后（右）半个区域继续进行折半查找若小于，则在前（左）半个区域继续进行折半查找。

③ 对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功，要么查找失败。折半查找的存储结构采用一维数组存放。

参考资料来源：百度百科-折半查找法

Answer 2

C.4