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

若数组 a 已按升序排列，下面函数能够返回最后一个小于等于 x 的元素下标；如果不存在，则返回 -1 。

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

看到题先想二分查找，因为数组已排序。关键观察是当 a[mid] <= x 时，记录 ans 并继续向右，否则向左。每一步推理的依据是二分查找的不变量：答案在 [l, r] 范围内，且 ans 记录当前找到的最后一个满足条件的下标。数值推演：假设数组 [1,3,5,7]，x=5，mid=2（5<=5），ans=2，l=3；mid=3（7>5），r=2；循环结束，返回 2，正确。

错误选项 B 可能让人误以为函数会漏掉某些情况，比如当 x 等于最后一个元素时，ans 是否会被正确更新。或者当数组只有一个元素时，函数是否正确处理。但实际函数能正确处理这些情况，所以 B 是错误选项。

1. 考纲定位

本题考查二分查找变体，位于 GESP 五级算法模块。命题人放这道题是为了考察学生对二分查找变体的掌握，特别是对最后一个满足条件的元素的定位，这是很多学生容易忽略的细节。

2. 解题思维

看到题先想二分查找，因为数组已排序。关键观察是当 a[mid] <= x 时，记录 ans 并继续向右，否则向左。每一步推理的依据是二分查找的不变量：答案在 [l, r] 范围内，且 ans 记录当前找到的最后一个满足条件的下标。数值推演：假设数组 [1,3,5,7]，x=5，mid=2（5<=5），ans=2，l=3；mid=3（7>5），r=2；循环结束，返回 2，正确。