C语言二分法查找

Python027

C语言二分法查找,第1张

#include <stdio.h>//不用math头文件

void main()

{int high = 9,low = 0,m,k,a[10]={1,2,3,4,5,6,7,8,9,10}//hing和low赋初值

scanf("%d",&k)

while (high>=low)//>=

{

m=(high+low)/2

if(k<a[m]) high=m-1//比较的是数值而不是下标

else if(k>a[m]) low=m+1

else

{

printf("yes")

return//这两句地方放错了

}

}

printf("no")

return//if语句去掉

}

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

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