加纳全年温度怎么样:二分查找，敢问谁对谁错？

来源：百度文库编辑：查人人中国名人网时间：2024/05/07 04:12:50

设一个有序线性表，有10个元素。用二分查找法查找某关键码。
问在查找成功和查找不成功的比较次数最多为多少？

对于以上问题，不同的书有以下两种不同的答案！

（1）查找成功和不成功时都为：log2（10）取整等于3次。
（2）查找成功时：log2(10+1)取整等于3次；查找不成功时log2(10+1)取整再加1等于4次。

以上哪个才是对的啊。还是都是对的呢。
http://zhidao.baidu.com/question/10935669.html

不成功的查找次数应该是log2(10)+1=4
成功的查找次数看你怎么定义成功了
如果你知道这个一定可以找到那么剩下两个时无论check哪一个都可以成功，这样就是log2(10)=3
如果不知道它一定在，那么最差情况还是要查两次所以也是要4次

这个你没必要抠得太细，其实最主要的是你要知道二分查找的时间复杂度是O(logN)

他这两个表达的意思都是一样的。

二分查找的终止条件是 1 关键码相等（找到时） 2 min > max （找不到时）就是说，因为mid = (min+max)/2，如果要找的小于key， max = mid-1, 反之 min = mid+1，如果找不到，这时min > max，程序退出，可能他指的是这个多出来的min和max的比较，把他算做一次，就是再加一次了。

两种答案都差不多，正如楼上仁兄所说，空间复杂度都可以认为是O(log n)

二分查找，敢问谁对谁错？谁对纸币一分、二分、五分感兴趣？如何编写一个函数,完成对数组的二分查找？如何编写一个函数,完成对数组的二分查找？解释二分查找算法^_^ 二分查找法的具体算法标准c库二分查找的函数采用二分查找的方法查找长度为N的..... 敢问谁能提供相声《各有所长》的剧本（台词）敢问谁有辽宁知名画家书法家的联系方式，联系地址？