Question

对22个记录的有序表做折半查找，当查找失败时，至少要比较 _______ 次关键字。

Answer 1

至少要比较4次关键字。

16<=22<31
所以查找失败时至少比较4次。这个值就是从折半查找判定树的情况推导出来的，上面4层是一个满二叉树，树高5层。

扩展资料：

折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数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，说明没有此数，打印找不到信息，程序结束。

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

Answer 2

应该是5次吧，树高应该是log2(22)也就是4次，但是还有一次是判断最后一次是不是NULL指针，如果是NULL就是失败，应该是log2(22)向下取整加一
个人拙见，如果有错误欢迎提出

Answer 3

16<=22<31
所以查找失败时至少比较4次

追问

能具体一点吗？谢谢！

追答

这个值就是从折半查找判定树的情况推导出来的，上面4层是一个满二叉树，树高5层

追问

好像明白了，但是我觉得应该是15<22<31这个式子，对吗？

追答

差不多，这个小于等于就是保证了判定树有5层，而且不是满二叉树