二分查找算法，二分查找算法举例说明

一、二分查找最坏查找次数计算公式

二分查找法最坏情况

n个数，比较中间的数，一次去掉一半，余下n/2个

n/2个数，再比较中间的数，一次去掉一半，余下n/4个

n/4个数，再比较中间的数，一次去掉一半，余下n/8个

n/8个数，再比较中间的数，一次去掉一半，余下n/16个

二、二分法次数计算公式

（n+1）/2=5.5

1次,精度1

2次精度0.5

3次精度0.25

4次精度0.125

5次精度0.0625

所以5次

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

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

三、二分查找算法遇到小数怎么办

如果是下标之和除以2得到的小数，这个直接下取整，也就是去掉那个0.5