1240：查找最接近的元素——二分索引

【题目描述】
在一个非降序列中，查找与给定值最接近的元素。

【输入】
第一行包含一个整数n，为非降序列长度。1≤n≤100000。

第二行包含n个整数，为非降序列各元素。所有元素的大小均在0−1,000,000,000之间。

第三行包含一个整数m，为要询问的给定值个数。1≤m≤10000。

接下来m行，每行一个整数，为要询问最接近元素的给定值。所有给定值的大小均在0∼1,000,000,000之间。

【输出】
m行，每行一个整数，为最接近相应给定值的元素值，保持输入顺序。若有多个值满足条件，输出最小的一个。

【输入样例】
3
2 5 8
2
10
5
【输出样例】
8
5

分析

1. 此题就是给个数看看，离序列哪个数近，就是二分查找，当然也可以用stl里面的lower_bound直接找出来，我这里手写的二分，二分序列的索引，找与想查的值k之间的差值，差值越小，那么他就是最近；
2. 若有多个值满足条件，输出最小的一个。当 当前的a[mid]小了，我也会if (abs(a[mid] - k) < abs(ans - k))判断保存一下，然后等他向大的找，如果差值和上次的一样，那此时也不会记录，因为if (abs(a[mid] - k) < abs(ans - k))用的是小于，没有等于，所以就解决了上面的多个值满足条件，输出最小的一个；

#include

using namespace std;

int n, m, t;
int a[100005];

//二分索引
int find(int k) {
    int ans = 0x3f3f3f3f;
    int l = 1, r = n, mid;
    while (l <= r) {
        mid = l + (r - l) / 2;
        if (a[mid] > k) {
            //大了
            if (abs(a[mid] - k) < abs(ans - k))
                ans = a[mid];
            r = mid - 1;
        } else if (a[mid] < k) {
            //小了
            if (abs(a[mid] - k) < abs(ans - k))
                ans = a[mid];
            l = mid + 1;
        } else {
            //刚刚好
            return k;
        }
    }
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> m;
    while (m--) {
        cin >> t;
        cout << find(t) << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45