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

令在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)┓

（向上取整）

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

  对具有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个元素。所以，平均的比较次数大概如下：

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

用二分法求方程的近似解

qq296127621,你好.

二分法的基本原理是连续函数的零点定理,表述及证明如下.

设函数f(x)在闭区间[a,b]上连续，且f(a)与f(b)异号（即f(a)×f(b)0），那么在开区间（a,b）内至少有函数f(x)的一个零点，即至少有一点ξ（aξb）使f(ξ)=0。证明：不妨设f(a)0,f(b)0.令E={x|f(x)0,x∈[a,b]}.由f(a)0知E≠Φ,且b为E的一个上界，于是根据确界存在原理，存在ξ=supE∈[a,b].下证f(ξ)=0（注意到f(a)≠0,f(b)≠0,故此时必有ξ∈(a,b).）.事实上，(i)若f(ξ)0,则ξ∈[a,b).由函数连续的局部保号性知存在x1∈(ξ,b):f(x1)0→存在x1∈E:x1supE,这与supE为E的上界矛盾；(ii)若f(ξ)0,则ξ∈(a,b].仍由函数连续的局部保号性知存在δ0,对任意x∈(ξ-δ,ξ):f(x)0→存在δ0,对任意x∈E:xξ-δ,这又与supE为E的最小上界矛盾。综合(i)(ii)，即推得f(ξ)=0。我们还可以利用闭区间套定理来证明零点定理。

如果没学过高等数学理解不了上面的证明也没关系.只需要注意一条连续的线,一头在X轴上方,一头在下方,那么这个线至少穿过X轴一次.这个与X轴的交点就是方程的根.现在用实例来解答.

比如求Y^3+Y-10=0的在区间Y[0,3]之间的根,先将Y=0代入方程左边,左边=-10,将Y=3代入左边,左边=20,这样已经创造出了一正一负,在0-3之间必有解,找中点.Y=1.5代入,如果是正,就保留负的那一头,如果是负就保留正的那一头,然后重复这一过程,不断找中点,只到等式左边接近或等于零,就解得了近似根或准确根.

希望我的回答对你有用.