在154个元素组成有序表进行二分法查找，可能的比较次数为

[不定项选择题]

在154个元素组成有序表进行二分法查找，可能的比较次数为？

```
10
```
```
8
```
```
4
```
```
1
```

查看答案及解析

奋斗吧少年

折半查找过程可用二叉树来描述，把有序表中间位置上的结点作为树的根结点，左子表和右子表分别对应树的左子树和右子树。折半查找的过程就是走一条从根节点到被查结点的一条路径，比较的次数就是该路径中结点的个数，即，该结点在树中的层数。所以该题可以转换为求有154个结点的二叉树有几层，小于等于这个层数的数值就是答案。又知，深度为K的二叉树最多有2的K次方-1个结点，深度为7的二叉树最多有127个结点，深度为8的二叉树最多有255个结点，所以154个结点的二叉树有8层。

发表于 2016-04-02 16:26:46 回复(7)

牛客749711号

[log2(154)] = 7，最差的情况下找8次，所以8次及8次以内都有可能找到。

发表于 2016-03-24 10:18:47 回复(5)

runner

为什么是按2的次方来算？二分法不是会每次减一吗。。这样的话2的n方就不准确了啊！我在纸上推算和代码测试了最多都只有7次。。求解答

发表于 2016-03-24 12:08:03 回复(9)

白起丶

用二分查找法查找某个数据，最多需要比较(logn)+1次，注意这里的对数函数是以2为底，并且是向下取整

发表于 2020-07-10 11:51:58 回复(0)

有梦为马，随处可栖

最开始我认为2⁸⁼256就没选B。原来是欠考虑了。二分查找可以看做是对二叉树的查找，对于完全二叉树而言，一层树为一个结点，二层树为3个，三层为8-1 (2的三次方-1)。。。。七层2⁷-1= 127，剩下的还能组成一层结点，所以是8层

发表于 2017-07-13 21:45:36 回复(0)

传琦

通过判定树可以描述二分查找过程，查找成功的最大次数为：log₂n(取下限)，查找不成功的次数为log ₂ n(取下限)+1；

因此 154个元素组成有序表进行二分法查找，最多比较次数为查找不成功的的次数： log ₂ n(取下限)+1=8

编辑于 2016-07-20 11:44:15 回复(0)

wanlanwalan

过程可用二叉树来描述，把有序表中间位置上的结点作为树的根结点，左子表和右子表分别对应树的左子树和右子树。折半查找的过程就是走一条从根节点到被查结点的一条路径，比较的次数就是该路径中结点的个数，即，该结点在树中的层数。所以该题可以转换为求有154个结点的二叉树有几层，小于等于这个层数的数值就是答案。又知，深度为K的二叉树最多有2的K次方-1个结点，深度为7的二叉树最多有127个结点，深度为8的二叉树最多有255个结点，所以154个结点的二叉树有8层。

发表于 2017-04-26 15:22:04 回复(0)