C++如何在有序数组中查找与给定数值最接近元素的下标

需求说明 #

在给定有序整数数组中，查找与输入目标数字最接近的元素对应的下标。
参考示例：

有序升序数组：{1,10,11,17,34,64,72}
输入目标值12，最接近的元素是11，对应下标为2（从0开始计数）

实现方案 #

方案1：二分查找（推荐，有序数组场景时间复杂度O(logn)） #

利用有序数组的特性，通过二分法快速定位插入位置，再比较相邻元素得到最接近值的下标，适合大数组长数组场景。
代码实现：

#include <vector>
#include <cmath>
#include <algorithm>

int closest_val(std::vector<int> vals, int digit) {
    // 边界判断：数组为空返回非法下标-1
    if (vals.empty()) {
        return -1;
    }
    // 数组只有一个元素直接返回0
    if (vals.size() == 1) {
        return 0;
    }
    // 二分查找第一个大于等于目标值的位置
    auto it = std::lower_bound(vals.begin(), vals.end(), digit);
    // 如果目标值比所有元素都大，返回最后一个下标
    if (it == vals.end()) {
        return vals.size() - 1;
    }
    // 如果目标值比所有元素都小，返回第一个下标
    if (it == vals.begin()) {
        return 0;
    }
    // 比较当前位置和前一个位置的元素哪个更接近目标值
    int curr_idx = it - vals.begin();
    int prev_idx = curr_idx - 1;
    if (abs(vals[curr_idx] - digit) < abs(vals[prev_idx] - digit)) {
        return curr_idx;
    } else {
        // 差值相等时返回靠前的下标，如需返回靠后的可改成return curr_idx
        return prev_idx;
    }
}

调用测试：

// 注意输入为升序有序数组
closest_val({1,10,11,17,34,64,72}, 12);
// 输出结果：2

方案2：遍历查找（支持无序数组，时间复杂度O(n)） #

如果输入数组为无序状态，可直接遍历所有元素记录最小差值对应的下标：

#include <vector>
#include <cmath>
#include <climits>

int closest_val(std::vector<int> vals, int digit) {
    if (vals.empty()) {
        return -1;
    }
    int min_diff = INT_MAX;
    int res_idx = 0;
    for (int i = 0; i < vals.size(); i++) {
        int diff = abs(vals[i] - digit);
        if (diff < min_diff) {
            min_diff = diff;
            res_idx = i;
        }
    }
    return res_idx;
}

注意事项 #

• 上述代码返回下标默认从0开始计数，若需要从1开始计数，直接将返回结果加1即可
• 若存在两个元素与目标值差值完全相等，上述实现默认返回下标更小的元素，可根据业务需求调整判断逻辑
• 二分查找方案默认数组为升序排列，若为降序数组可替换std::lower_bound为std::upper_bound并传入std::greater<int>()比较器即可

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