已知一个长度为16的有序顺序表R[1..16]，采用折半查找方法查找一个存在的元素，则比较的次数最多_

学习人数: 4.5k

正确率: ??%

题目描述

未通过

已知一个长度为16的有序顺序表R[1..16]，采用折半查找方法查找一个存在的元素，则比较的次数最多是______。

A. 5

B. 4

C. 7

D. 6

上面问题的答案是：

A 选项

B 选项

C 选项

D 选项

加入错题本

个人笔记

已有18条笔记

3 个回答 (点击展开回答)

2024年10月27日 21:39

1-16 -》（1+16）/2=8，第一次

1-7-》（1+7）/2=4 第二次

1-3-》（1+3）/2=2第三次

1-1-》（1+1）/2 = 1 第四次

admin 回复小灰机：有个简单的方法，你这样想4个数折半查找两次能不能找到，很明显最坏情况要比较三次。实际上这题考察二叉排序树的是否理解，16个元素的二叉排序树深度最低为5。

2024年10月27日 22:50

2024年9月14日 18:05

16个二叉排序树的深度为5，查找一个不存在的最多查到最后一层，即5

log2(16)+1=5

2024年7月20日 11:21

对于长度为 nnn 的有序表，比较的次数最多为log2 n，加一次失败比较次数，所以为4+1

秀秀回复 17679377259：题目不是查找存在的元素吗

2024年9月5日 14:47

17679377259 回复秀秀：是的，我当时搞错了。应该是该二叉判定树高度，而不需要加失败比较次数，所以公式应该是高度公式，log n 取下界+ 1或log (n+1)取上界

2024年9月5日 21:00