Binary Search - A

public
yeskendir.sultanov Mar 31, 2024 Never 56
Clone
C++ Abinsearch.cpp 43 lines (37 loc) | 902 Bytes
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
5
int main() {
6
std::ios_base::sync_with_stdio(false);
7
cin.tie(0);
8
cout.tie(0);
9
int n, k;
10
cin >> n >> k;
11
int a[n];
12
for (int i = 0; i < n; ++i) {
13
cin >> a[i];
14
}
15
16
for (int i = 0; i < k; ++i) {
17
int x;
18
cin >> x;
19
int L = 0, R = n - 1, fi = -1;
20
while (L <= R) {
21
int mid = (L + R) / 2;
22
if (x < a[mid]) {
23
R = mid - 1;
24
} else if (a[mid] < x) {
25
L = mid + 1;
26
} else {
27
fi = i;
28
break;
29
}
30
}
31
32
if (fi != -1) {
33
cout << "YES" << endl;
34
} else {
35
cout << "NO" << endl;
36
}
37
}
38
39
return 0;
40
}
41
42
// Time Complexity: O(K * logN)
43
// time = 10^5 * 17 / 10^8 = 0.017 sec