如何实现C++ STL upper_bound的反向效果，返回目标值左侧更小元素

结论 #

你当前的实现是完全正确的，无需手动实现二分搜索，STL提供的标准接口已经可以满足需求。

原理解释 #

STL中upper_bound的通用逻辑是：在已按照comp规则升序排列的区间中，返回第一个满足comp(传入值, 迭代器指向元素) == true的迭代器。

你使用了反向迭代器rbegin()/rend()，相当于把原非递减数组反转成了非递增序列，同时传入greater<int>()作为比较规则，此时upper_bound会在反转后的序列中找到第一个满足「301 > 元素」的位置，对应原数组中就是小于301的最大元素，和你的预期完全匹配。

你补充的边界判断if (p != arr.rend())也是正确的：如果没有比目标值更小的元素，upper_bound会返回rend()，此时直接访问*p会出现未定义行为，提前判断可以规避风险。

更直观的替代实现 #

如果你不想用反向迭代器，也可以基于正向迭代器实现相同效果，逻辑更易读：

// 非递减数组中找小于value的最大元素
auto p = lower_bound(arr.begin(), arr.end(), value);
if (p != arr.begin()) {
    --p;
    cout << *p << endl; // 得到目标值
} else {
    cout << "没有更小的元素" << endl;
}

这个实现的逻辑是：lower_bound会返回第一个大于等于value的元素位置，只要这个位置不是数组开头，往前挪一位就是小于value的最大元素。

代码验证 #

以你给出的测试数组为例，两种实现的输出都是-550，完全符合预期。

内容的提问来源于stack exchange，提问作者Mayukh Sarkar