GESP 五级 · GESP202609 C++ 五级 第 9 题

在升序数组中查找第一个严格大于 x 的元素位置，下面代码中的横线应填写（　　）。

int upperBound(const vector<int> &a, int x) {
int l = 0, r = (int)a.size();
while (l < r) {
int mid = l + (r - l) / 2;
if (__________________) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}

二分查找框架，维护区间 [l,r) 表示答案一定在此范围内。每次取中点 mid，根据 a[mid] 与 x 的关系决定答案在左半还是右半：若 a[mid] 满足"太小"条件，则 l=mid+1 向右收缩；否则 r=mid 向左收缩。循环终止时 l=r 即为所求位置。

选项 A 漏掉等于情况，若 a[mid]==x 却误判为"太小"，会跳过正确答案；选项 B 把等于也归为"太大"，同样会漏掉第一个大于 x 的元素；选项 D 条件反向，会导致 l 一直右移，最终返回数组末尾。边界上 a[mid]<=x 时 l=mid+1 保证不会越界，循环条件 l<r 确保至少执行一次。

1. 考纲定位

本题考查二分查找在 GESP 五级中的标准应用。命题人刻意选用"第一个严格大于 x"的表述，卡住的是学生容易混淆"上界"与"下界"二分，以及条件判断方向。

2. 解题思维

看到题先想：答案在某个区间内，二分每次把区间减半。关键观察是：若 a[mid]<=x，则 mid 及左侧都不可能是第一个大于 x 的元素，答案必在 (mid,r) 中，所以 l=mid+1；反之 a[mid]>x 时，mid 可能是答案，但左侧也可能有更小的满足位置，答案在 [l,mid)，所以 r=mid。

数值推演：设 a=[1,3,5,7,9]，x=4。初始 l=0,r=5。mid=2，a[2]=5>4，r=2；mid=1，a[1]=3<=4，l=2；mid=2，l=r 退出，返回 2，正确指向 5。