Question

C语言 二分法查找次数公式怎么推导？

求大神给我讲一讲二分法（数组数对应的查找次数的推导）

Answer 1

    对具有n个元素的有序数组进行二分法查找，要分析的比较次数，可以使用画二叉判定树的方法来分析。该二叉判定树的高度为[log2(n)]+1层，此即为二分查找的最多比较次数，比如：n=1000，则最多比较[log2(1000)]+1=9+1=10次。

    如果要计算平均的比较次数，则需要对二叉判定树中的每个节点进行分析，处于第一层的比较1次，第二层的比较2次，第三层比较3次，依次类推……把各个节点的比较次数累加，再处于节点数（元素个数）即为平均比较次数，这里假设查找是在等概率的情况下进行的。

    举个例子：有9个元素的有序数组，对每个元素按1,2,3...8,9进行编号，则其二叉判定树如下：

图中可以看出，如果要找的元素处在第5个位置，则只要1次比较即可找到，若找第9个元素，则需要4次比较，算法分别比较了第5,7,8,9等4个元素。所以，平均的比较次数大概如下：

这样分析，能看懂吗？希望能帮到你！

追问

你有那个数据结构和算法的皮皮替可不可以发给我呢？

追答

对不起，这个ppt是内部资料，不能随便外传的！

追问

那110个数，最多查找几次？

追答

最多查找 [log2(110)]+1=7 次

追问

但是书上说是8次

而且公式是log2（N-1）+2

追答

你看的书写错了，公式也错！即使是查找不成功，也最多比较7次。
110个数，画成二叉判定树，各层的节点数分别是：
1
2
4
8
16
32
47

等概率情况下，查找成功的平均比较次数为：(1*1+2*2+3*4+4*8+5*16+6*32+7*47)/110=650/110≈5.91次。

Answer 2

令在a[i]~a[j] (j-i=n-1) 这n个有序的元素中查找元素x的查找次数为f(n)，则：

f(n)=1 若中点查找匹配 （a[m]=x ， m=(i+j)/2）
=f(n/2)+1 若中点查找不匹配，a[m]!=x
其中的/为整数除法
最多查找次数为f1(n)=┏Log2(n+1)┓ （向上取整）

追问

能不能用笔写一写，然后照一张相，发给我，谢谢你～～

……

追答

分析：
在1个元素中找，当然只要找1次；
在2个元素中找，最坏可能要找2次；
在3个元素中找，首先与中间一个，即a[2]比，若不是，则排除一半，在剩余的1个中找，最坏可能要找2次（1+1＝2次）；
在4个元素中找，首先与a[2]比，若不是，则排除一半，最坏的可能在剩余的2个中找，除已比的一次外，最坏可能还要找2次（见第3行）；于是最多是找1+2＝3次
………………
这是上面递推公式的分析，
至于直接计算的公式，就需要比较扎实的高中数学基础。

追问

两个元素的时候最坏找一次吧，第一次比较不是需要的元素，那么剩下的元素就是需要的元素。

追答

也有可能那不是要找的数据啊.
只有23,56
要找76,那要找2次才能确定没有的.

追问

哦哦