Приближенный поиск

 avatar
unknown
c_cpp
a year ago
819 B
20
Indexable
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int a[n];
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        int x;
        cin >> x;
        int L = 0, R = n - 1, k = -1;
        while (L <= R) {
            int m = (L + R) / 2;
            // a[k-1] < x <= a[k]
            if (x <= a[m]) {
                k = m;
                R = m - 1;
            } else {
                L = m + 1;
            }
        }

        if (k == -1) {
            cout << a[n - 1] << endl;
        } else if (k == 0) {
            cout << a[0] << endl;
        } else if (x - a[k - 1] <= a[k] - x) {
            cout << a[k - 1] << endl;
        } else {
            cout << a[k] << endl;
        }
    }
    return 0;    
}





Editor is loading...
Leave a Comment