GESP 五级 · GESP 202512 C++ 五级 第 11 题

下面代码尝试在有序数组中查找第一个大于等于 $x$ 的元素位置。如果没有大于等于 $x$ 的元素，返回 arr.size()。以下说法正确的是（ ）。

int lower_bound(vector<int>& arr, int x) {
    int l = 0, r = arr.size();
    while(l < r) {
        int mid = l + (r - l) / 2;
        if(arr[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】二分查找｜边界条件处理｜半开区间查找

考纲定位：本题位于 GESP 五级"算法与数据结构"模块，卡住的是考生对二分查找边界条件的理解。命题人专门设计此题，就是要区分那些只会背"二分查找代码模板"却不懂区间不变量的学生——很多人错误地把循环条件写成 l ≤ r，导致死循环。

解题思维：二分查找的核心是维护一个不变量：答案一定在 [l, r) 区间内。初始时 l = 0, r = n，循环条件 l < r 确保区间非空。每次 mid = l + (r - l) / 2，如果 arr[mid] >= x，说明答案在 [l, mid]，所以 r = mid；否则答案在 [mid + 1, r)，l = mid + 1。循环终止时 l == r，即为答案。通法是：对于"第一个满足条件"的问题，用 l < r 循环，r = mid 或 l = mid + 1。

陷阱拆解：选项 B 把 l < r 改成 l ≤ r，当 l == r 时仍会执行，而 mid 计算后 r 可能小于 l，但循环条件仍成立，导致死循环。选项 C 认为 mid 计算错误，但 l + (r - l) / 2 是标准写法，没有溢出风险。选项 D 说边界条件不对，但代码正确返回 arr.size() 表示未找到。命题人利用的是考生对二分查找区间表示的混淆，很多人习惯用闭区间 [l, r]，但这里用半开区间 [l, r)，导致误解。

反命题思维：如果把题目改成"查找最后一个小于等于 x 的元素"，代码只需把 if 条件改为 arr[mid] <= x，然后 l = mid，r = mid + 1，循环条件仍为 l < r。或者改成查找第一个严格大于 x 的元素，只需把 if 条件改为 arr[mid] > x，r = mid，l = mid + 1。命题人可能想考"第一个大于 x 的元素"与"第一个大于等于 x 的元素"的区别，容易混淆。