c语言二分查找,c语言二分查找算法

大家好，今天小编关注到一个比较有意思的话题，就是关于c语言二分查找的问题，于是小编就整理了3个相关介绍c语言二分查找的解答，让我们一起看看吧。

1. 二分法次数计算公式？
2. 关于数据结构二分法查找成功的平均查找长度和失败的查找长度？
3. 关于折半查找的比较次数？

二分法次数计算公式？

（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次，依次类推……把各个节点的比较次数累加，再处于节点数（元素个数）即为平均比较次数，这里***设查找是在等概率的情况下进行的。

关于数据结构二分法查找成功的平均查找长度和失败的查找长度？

做这种的时候，应该画出二叉树。然后把叶子补足。叶子的高度就是查找失败的次数。然后求和除以叶子数目就是失败的平均查找长度。而非叶子节点就是成功的，高度就是成功的查找次数，然后除以非叶子节点的数目，就是成功的平均长度。对于11个节点，其构成的二叉树成功的查找长度是(1x1+2X2+3x4+4x4)/11=33/11失败的查找长度是(4x8+3x4)/(8+4)=44/12

关于折半查找的比较次数？

第五个查找1次 第二个和第七个查找两次 第一，第三和第六，第八要查找三次 第四和第九要查找四次 一共25次 ASL=25/9 查找值为21的结点，需要比较2次。

到此，以上就是小编对于c语言二分查找的问题就介绍到这了，希望介绍关于c语言二分查找的3点解答对大家有用。

标签： 查找 比较 次数