Question

折半查找法的平均查找长度是多少？

Answer 1

折半查找的平均长度是3.1。

12个关键字的有序表，折半查找的判定树如下：

6

/           \

3      9

/     \       /     \

1   4   7   11

\        \     \          /      \

2 5     8      10     12

平均查找长度=1/12*(1*1+2*2+3*4+4*5)=37/12。=3.1。

扩展资料：

折半查找法效率较高。

假设有已经按照从小到大的顺序排列好的五个整数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，说明没有此数，打印找不到信息，程序结束。

该方法是查找的范围不断缩小一半，所以查找效率较高。

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