如何在有序正整数数组中查找最接近的较小值？优先用C++ <algorithm>库

给定有序正整数数组：

std::vector<int> numbers = { 0, 4, 12, 60, 89 };

要求用最简单的方法，基于<algorithm>库查找输入值对应的最接近的较小值（规则：输入值存在则返回自身；输入值大于所有元素返回最后一个元素；输入值小于所有元素返回第一个元素）。

示例 #

解决方案 #

使用<algorithm>中的std::upper_bound是最优且最简单的方案，该函数通过二分查找（时间复杂度O(log n)）定位第一个大于目标值的元素，只需将迭代器回退一位即可得到结果：

#include <vector>
#include <algorithm>

int findClosestSmaller(const std::vector<int>& nums, int target) {
    // 查找第一个大于target的元素迭代器
    auto it = std::upper_bound(nums.begin(), nums.end(), target);
    // 兜底处理：所有元素都大于target的情况（题目场景下极少出现）
    if (it == nums.begin()) {
        return nums.front();
    }
    --it;
    return *it;
}

逻辑说明 #

1. std::upper_bound依托数组有序特性，快速定位第一个大于目标值的位置
2. 迭代器回退后，指向的元素要么等于目标值（目标存在时），要么是小于目标值的最大元素
3. 边界适配：当目标值大于所有元素时，it指向nums.end()，回退一位即为数组最后一个元素；当目标值小于所有元素时，直接返回数组首元素

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