将数据元素2,4,6,8, 10, 12, 14, 16,

[单选题]

将数据元素2,4,6,8, 10, 12, 14, 16, 18,20, 22依次存放于一个一维数组中，然后采用折半查找方法查找数组元素16,被比较过的数组元素的轨迹依次为（）

```
12,18,14,16
```
```
12,14, 18,16
```
```
6,9,7,8
```
```
6,7,9,8
```

查看正确选项

川久保玲球

一维数组str[]：

下标	0	1	2	3	4	5	6	7	8	9	10
值	2	4	6	8	10	12	14	16	18	20	22

折半查找的实现过程：先确定查找的所在范围，然后逐渐缩小这个范围，直到找到该记录或查找失败（查无该记录）为止

设指针low，high分别指向查找范围的上界和下界，指针mid指向查找范围的中间位置，即 mid = (low + high) / 2

Step 1：low = 0, high = 10, mid = (low + high) / 2 = 5, 被比较过的数组元素为 str[5] = 12

key = 16 > 12, low = mid + 1 = 6, high = 10

Step 2：mid = (low + high) / 2 = 8, 被比较过的数组元素为str[8] = 18

key = 16 < 18, low = 6, high = mid - 1 = 7

Step 3：mid = (low + high) / 2 = 6, 被比较过的数组元素为str[6] = 14

key = 16 > 14, low = mid + 1 = 7, high = 7

Step 4：mid = (low + high) / 2 = 7, 被比较过的数组元素为str[7] = 16

key = 16, 查找成功

被比较过的数组元素的轨迹依次为 12，18，14，16

编辑于 2020-07-10 15:34:09 回复(3)

LauZyHou

如果剩下的子序列有奇数个数字，就取中间那个为middle。如果有偶数个数字，取前一半的最后一个为middle。

发表于 2019-03-27 09:53:44 回复(0)

Furimlee

首先对数组进行排序，查找数组中中间数与需要查找元素匹配，中间数12<16,说明在该数在12右侧。12右侧5个数中中间数18，16<18,说明在12右侧和18左侧，依次比较14 16

发表于 2019-07-05 15:13:32 回复(0)

牛客46920278号

一共是11个元素，第一次查找第6个元素12，12＜16，在中间元素右侧继续二分查找。 12右侧剩五个元素，mid就是第3个元素18，16＜18 ，在18左侧二分查找。 18左侧就只剩14和16了，偶数个元素取前一半的最后一个元素为mid，就是14，最后剩个16。

发表于 2022-03-17 11:24:26 回复(1)

初一十五三十

这个一维数组A的长度是11。

因此，第一个比较的元素是A[11/2]=A[5]=12；第二个比较的元素是A[(6+11)/2]=A[8]=18；第三个比较的元素是A[(6+7)/2]=A[6]=14；第四个比较的元素是A[(7+7)/2]=A[7]=16。

发表于 2019-09-09 10:43:05 回复(2)

jon110

不应该是12 18 16吗

发表于 2019-03-25 01:58:16 回复(2)

牛客412161345号

首先假设表中元素按升序排列，将表中间位置记录的关键字和查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找的关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，则查找成功，或直到子表不存在为止，此时查找不成功。

发表于 2018-08-14 22:06:10 回复(0)