aoj 二分探索

ALDS1_4_B Search - Binary Search

ALDS1_4_B Search - Binary Searchの問題と解答例.
Feb. 2, 2020, 1:52 p.m.

目次

問題

解答

 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
inline bool search(vector<ll> v, ll target) {
    if (target < v[0] || v[v.size()-1] < target) return false;

    ll left = 0, right = v.size(), mid;
    while (left < right) {
        mid = (left + right) / 2;
        if (v[mid] == target) return true;
        else if (v[mid] < target) left = mid+1;
        else right = mid;
    }

    return false;
}

int main(void) {
    ll n, q, x;
    vector<ll> vs, vt;

    cin >> n;
    ll i = 0;
    loop(i, 0, n) {
        cin >> x;
        vs.push_back(x);
    }

    cin >> q;

    ll count = 0;
    loop(i, 0, q) {
        cin >> x;
        if (search(vs, x)) count++;
    }

    cout << count << endl;
}