我要招人

去企业版

首页 > 试题广场 >

若有一个顺序有序表A[1:18] 中有18个元素，现进行二分

[单选题]

若有一个顺序有序表A[1:18] 中有18个元素，现进行二分查找，则查找 A［3］的比较序列的下标依次为（）。

```
1，2，3
```
```
9，5，2，3
```
```
9，5，3
```
```
9，4，2，3
```

查看正确选项

ShaoXiaobao

假设[1:18]是单调递增，设A[3] = x。

先查找[1:18]的中间值mid=（1+18）/2=9.5，向下取整为9,

A[9] > x，于是范围变成了中值左边的取值，左右值变成了[1:9-1]即为[1:8]

mid =（1+8）/2=4.5，取值4

A[4] > x，于是范围变成了中值左边的取值，左右值变成了[1:4-1]即为[1:3]

mid = (1+3)/2 = 2

A[2] < x，于是范围变成了中值右边的取值，范围变成[2+1:3]即为[3:3]

A[3] = X

由上：查找 A［3］的比较序列的下标依次为（9,4,2,3 ）。

发表于 2017-08-04 09:19:48 回复(0)

Given

[a,b] 的中间元素为（a+b）/2向下取整

1~18：（1+18）/2 向下取整=9

3<9，因此下一次范围是1~8，（1+8）/2向下取整=4

3<4，因此下一次范围是1~3，得2

2>3，因此下一次范围是3~3，的3

发表于 2017-08-03 23:30:46 回复(0)

武培轩

正确答案

答案解析

设要查找A[3]为x；

第一次查找，index =（1+19）/2 =9.5，向下取整 index = 9；

A[9]>x，index=(1+8)/2=4.5，向下取整index=4；

A[4]>x，index=(1+3)/2=2；

A[2]<x，index=（3+3）/2=3;

A[3]=x；

于是查找A[3]的序列为9，4，2，3

发表于 2018-09-13 17:11:16 回复(0)

锅炉师傅的铲子

向下取整，剔除中间元素

发表于 2018-02-27 12:06:56 回复(0)

我是超越迷妹了😘

每次比较的点都为[low+high]/2的结点，若该点大于mid则low=mid+1;若小于mid,则high=mid-1.此时重新求mid

发表于 2017-08-06 21:33:02 回复(0)

DanielTYL

记住是向下取整，不然容易出错了

发表于 2017-09-15 00:22:34 回复(0)

牛客260645721号

侧移一位

发表于 2022-03-23 08:07:45 回复(0)

黄昏里的男孩

WOC 二分查找的时候老是忘记指针要侧移一位！

发表于 2018-03-07 16:12:15 回复(0)

牛客9277021号

发表于 2018-02-26 23:53:32 回复(0)

Duange

发表于 2017-12-24 23:03:16 回复(0)

大王派我来巡山哟

953

发表于 2017-12-15 16:34:04 回复(0)

刘灵均____

发表于 2017-12-12 16:40:18 回复(0)

猪猪侠来啦

发表于 2017-10-22 14:01:22 回复(0)

喵布丁

向下取整

发表于 2017-09-05 19:57:20 回复(0)

RiseSun

发表于 2017-08-04 10:23:56 回复(0)

牛客9895611号

发表于 2017-08-03 21:13:37 回复(0)

提交观点

问题信息

查找

上传者：赞花婆

难度：

16条回答 364收藏 5060浏览

若有一个顺序有序表A[1:18] 中有18个元素，现进行二分

问题信息

热门推荐

相关试题