首页 > 试题广场 >

在顺序表{12,15,17,20,24,30,38,43,4

[单选题]

在顺序表{12,15,17,20,24,30,38,43,45,51,52}中，用二分法查找关键字20需做（）次关键字比较。

查看正确选项

ColorfulBlack

以上一共11个数，按下标则是0..10，以下按照步骤进行

1、mid=（left + right）/ 2 = (0 + 10) / 2 = 5，即第一次使用目标值20与下标为5的值30进行比较，20<30，则 right = mid - 1 = 4；

2、mid=（left + right）/ 2 = (0 + 4) / 2 = 2，即第二次使用目标值20与下标为2的值17进行比较，20>17，则 left = mid + 1 = 3；

3、mid=（left + right）/ 2 = (3 + 4) / 2 = 3，（int，向下取整），即第三次使用目标值20与下标为3的值20进行比较，20=20，返回下标3，算法结束。

综上所述，进行了3次比较，选B。

编辑于 2019-04-18 10:38:14 回复(3)

邓胜涛1

对半比，就是二分法，就类似于中分头😂

发表于 2018-10-25 10:04:28 回复(1)

牛客270887862号

表的下表从1开始吧

发表于 2021-03-11 16:59:16 回复(0)

夏弈

发表于 2020-07-02 08:19:27 回复(0)

牛客651205号

30-17-20

发表于 2018-09-02 17:50:15 回复(0)

努力努力再努力+1

第一次分前五个和后六个 20<24 在前五个分组里去找

第二次将1 2 、1 5 、1 7 、2 0 、2 4再次二分为12、15和17、20、24 ；20 > 15，在后三个分组中找

第三次 17、20、24可直接找到20

发表于 2017-09-03 10:10:03 回复(6)

提交观点

问题信息

查找

上传者：zsw3

难度：

6条回答 158收藏 1638浏览

扫一扫，把题目装进口袋