练56.2 查找最接近的元素

解题思路

非降序数组用lower_bound找首个≥x的元素。最接近者只可能是它或前一个，比较差值；差相同取前一个较小值。

正确性说明

按顺序完成所述运算后，每个输入元素都被处理在相应位置或统计项中。保存的中间状态与已处理数据对应，最终输出与题目定义一致。

易错点

处理查询小于首项、大于末项的边界，避免越界。

复杂度

时间O(n+m log n)，空间O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &v : a)
        cin >> v;
    int m;
    cin >> m;
    while (m--) {
        long long x;
        cin >> x;
        auto it = lower_bound(a.begin(), a.end(), x);
        if (it == a.begin())
            cout << *it;
        else if (it == a.end())
            cout << a.back();
        else {
            long long hi = *it, lo = *(it - 1);
            cout << (x - lo <= hi - x ? lo : hi);
        }
        cout << "\n";
    }
    return 0;
}