Question

对于长度为18的顺序存储的有序表,若采用折半查找,则比较4次就能查找的元素共有几

Answer 1

等概率下，折半查找的平均查找长度公式为：ASL={[(n+1)/n]*log2^(n+1)}-1。

折半查找原码是：

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

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

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

第一次和37比较，第二次和12比较，第三次和20比较，第四次和26比较，所以是4次。

扩展资料：

折半查找法：

假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是： 设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找；

否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；如此重复前面的过程直到找到或者l>h为止。如果l>h，说明没有此数，打印找不到信息，程序结束。

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