一个长度为32的有序表，若采用二分查找一个不存在的元素，则比

[单选题]

一个长度为32的有序表，若采用二分查找一个不存在的元素，则比较次数最多是__？

```
4
```
```
5
```
```
6
```
```
7
```

查看答案及解析

loveCoding

找不到元素需要logn + 1次，此题n为32，故答案应该是6.

发表于 2015-09-14 15:03:49 回复(0)

更多回答

水煮鱼

最方面的方法是建立一个判定树。

现在有11个数：（第1行是索引，第2行是数）

0	1	2	3	4	5	6	7	8	9	10
7	10	13	16	19	29	32	33	37	41	43

判定树：

圆形节点表示查找成功的节点，方形的是查找不成功的节点。

判定树展示了二叉查找的过程。

有：

查找成功的最少次数：1
查找成功的最多次数：4

查找成功的平均次数：(1*1+2*2+3*4+4*4) / (1+2+4+4) = 3

查找不成功的最少次数：3
查找不成功的最多次数：4
查找不成功的平均次数：（3*4+4*8）/(4+8) = 11/3

发表于 2017-09-29 15:44:23 回复(0)

牛客981559号

最坏无外乎分到最后
32 1
16 1
8 1
4 1
2 这时候比较最坏比较2次一共6次（除非里面必含所查元素是5次）

发表于 2016-08-22 16:40:21 回复(1)

有梦为马，随处可栖

log2ⁿ +1 （log2ⁿ向下取整）

发表于 2017-07-15 10:05:27 回复(0)

chouchou-小宠

如果查找存在的元素，最多需要的比较次数是几次？

发表于 2017-04-19 16:22:43 回复(0)

兔子的救兵

2^5=32

发表于 2015-09-14 13:27:21 回复(0)

峰风

这题其实是考察完全二叉树的深度问题，比较次数也就是深度，只含有一个节点的时候深度为1，假设深度为k，则有2^k-1>=n>2^(k-1)-1,其中2^k-1对应深度为k的满二叉树对应节点数，那么等价于2^k>=（n+1）>2^(k-1)，不等式两边同时取log，k>=log(n+1)>(k-1),此时k等于log(n+1)向上取整数，因此log（32+1）向上取整为6

发表于 2015-09-17 10:15:42 回复(1)