查找最接近的元素

题意

在非降序列中回答多次查询：输出与查询值距离最小的元素；距离相同则选较小值。

思路

bisect_left(numbers, target) 找到第一个不小于查询值的位置。最接近的元素只可能是这个位置或其左邻居；处理越界后比较两边距离。相等时选择左边，正好满足取较小值的规则。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19from bisect import bisect_left

input()
numbers = list(map(int, input().split()))
query_count = int(input())

for _ in range(query_count):
    target = int(input())
    right = bisect_left(numbers, target)
    if right == 0:
        print(numbers[0])
    elif right == len(numbers):
        print(numbers[-1])
    else:
        left = right - 1
        if numbers[right] - target < target - numbers[left]:
            print(numbers[right])
        else:
            print(numbers[left])

C++代码

cpp

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
46
47#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int a[maxn];
int n;
int m;
bool check(int m,int val){
    return a[m] >= val;
}
int bs_find(int l,int r,int val)
{
    while(l < r) {
        int mid = (l+r) >> 1;
        if( check(mid,val) == true) 
            r = mid;
        else 
            l = mid+1;
    }
    return l;
}

int main(){
    cin >> n;

    for(int i =1;i<=n;i++)
        cin >> a[i];
    // sort(a+1,a+1+n);
    cin >> m;
    for(int i =1;i<=m;i++){

        int t;
        cin >> t;
        int pos = bs_find(1,n+1,t);
        if( pos == n+1)
            cout << a[n] << endl;
        else if( pos == 1){
            cout << a[1] << endl;;
        }
        else if(a[pos] - t >= t-a[pos-1]){
            cout << a[pos-1] << endl;
        }
        else 
            cout << a[pos] << endl;
    }
    
    return 0;
}

复杂度

每次查询时间复杂度为 $O(\log n)$ ，额外空间复杂度为 $O(1)$ 。

总结

有序序列中的“最接近”问题，只需检查二分定位点附近的两个候选。

查找最接近的元素

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结