已知一个数值有序表{3, 6, 9, 12, 15, 18,

[单选题]

已知一个数值有序表{3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 35}，当二分查找值为31的元素时，查找失败的比较次数为（）（提示：mid = (low + high) / 2 向下取整）

```
3
```
```
4
```
```
5
```
```
6
```

查看答案及解析

以凝

题解的最后一次比较表述有问题。

1.  ‌第四次比较‌：

    *   此时 low = 9，high = 9
    *   计算 mid = (low + high) / 2 = (9 + 9) / 2 = 9
    *   比较 array[mid] = 30 与 31
    *   因为 30 < 31，所以更新 low = mid + 1 = 10
‌查找失败‌：

最后： 此时 low = 10，high = 9，因为 low > high，查找失败

btw 这里一般都默认条件是while(l<=r)
你如果用acwing给的二分模板，y总一般都是while(l<r),我也这种，就会少判断一次就会跳出循环。但那模板是对于二分答案的题目来讲的，而对于数组中寻找元素来说，最后一次仍然是有必要判断的，所以是四次比较没毛病。

发表于 2025-03-19 23:51:04 回复(1)

牛客733353188号

在二分查找中，有序表的索引通常从 0 开始（这是计算机领域中数组索引的常见起始方式），所以初始的low（表示查找范围的左边界）设为 0，high（表示查找范围的右边界）设为表中元素个数减 1（本题中元素有 12 个，所以high=11）。这样的设定是为了准确地定位数组中的元素位置，从而进行二分查找的区间划分。这里的mid、low、high都是索引值。当mid小于目标值，low=mid+1;当mid大于目标值，high=mid-1。

编辑于 2025-10-28 15:39:13 回复(0)