Question

C语言 二分法查找的问题？请大家帮我解惑。

看图

Answer 1

最坏的情况应该是log2n向下取整+1，这也是折半查找判定树(完全二叉树)的树高。
第一，题目不严谨，这个折半查找可以向上或向下取整(大部分参考书上默认用向下取整来讲解)，向下取整当然是花4次找到8，而向上取整是3次。
第二，最后剩下一个数的时候，那个数还需不需要比较，从代码层面来看，不能简单认为最后剩下的一个数就是所找的数，因为那个数可能并不在序列中，所以最后一次也应该比较。折半查找判定树也是这么定义的，所查找数字所在层的树高即比较次数。
至于那个结论，最坏情况下需要比较的次数，是一个等价无穷小的结论而已。因为比较次数是一个整数，结果可能是个小数，如果那个是最坏比较次数的具体答案的话，它还会指明它是向上取整还是向下取整。