NOIP 普及组初赛 · NOIP 2008 普及组初赛试题 第 15 题

对有序数组 $\{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100\}$ 进行二分查找，成功查找元素 $19$ 的查找长度（比较次数）是（ ）。

这题考二分查找的查找长度，拿到题先别急着算，先想二分的核心：每次取中点比较。数组长11，中点下标5对应56，比19大，说明目标在左半边，范围缩成0~4，再取中点2，正好是19，两步搞定。

最容易栽跟头的地方是把‘查找长度’理解成‘移动次数’或者‘访问次数’，其实它严格等于比较次数。有人会以为第一次比较后直接找到算1次，或者把左边界调整也算一次比较，导致选成1或3。还有人会混淆下标计算，比如把(0+10)/2算成6，从而多走一步。

这题考什么

这道题考查的是二分查找算法中的查找长度（也叫比较次数）。在初赛单选题里，命题人特别喜欢用这种‘看似简单但概念定义要抠字眼’的题来区分真正理解算法的学生和只会背步骤的学生。

知识点概念：二分查找是啥？

二分查找针对的是有序数组。它的核心思想是：每次把查找区间一分为二，通过比较中间元素和目标值的大小，直接排除掉一半不可能的区间。这样，每比较一次，搜索范围就缩小一半，效率极高。