A fast search method that finds targets in a sorted array by repeatedly cutting the search area in half.
Suppose we have a sorted array and we want to find the position of a value , i.e. such an index that . If does not exist in the array, we should return .
Example: and , Then the answer is position .
The first idea is to go from left to right and compare every element with .
This works because if exists, we will eventually find it. If the loop finishes, then there is no such value.
The problem is speed. One search takes time. For a large array and many queries, this is too much.
The array is sorted, so we can skip many elements at once. Instead of checking positions one by one, we look at the middle position .
This implementation does not directly search “any equal ”. It first finds the first position where . After the loop, we check if this position really contains .
For example, let and . Binary search finds the first position where the value is at least . That position has value , so we return it.
For: and , binary search finds the first position where the value is at least , which is value . But , so the answer is .
Before the loop, we must choose the borders correctly. Because our array is 1-indexed, the first possible position is and the last possible position is . So we write:
The meaning is: if the answer exists, it is somewhere inside the current range .
Algorithm:
Each step removes about half of the current range, so the search becomes very fast.
1. Start with l = 1 and r = n.
2. While l < r:
1. Let m = (l + r) / 2.
2. If a[m] < x, then elements in positions [l, l + 1, ..., m] are too small. Set l = m + 1.
3. Otherwise, a[m] >= x, so the answer can be at m or before it. Set r = m.
3. Now l = r, so only one candidate remains.
4. If a[l] = x, return l.
5. Otherwise, return -1.
int find_linear(int x) {
for (int i = 1; i <= n; i++) {
if (a[i] == x) {
return i;
}
}
return -1; // if x doesn't exist in array
}
int l = 1;
int r = n;
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, q;
int a[N];
int binary_search_any(int x) {
int l = 1;
int r = n;
while (l < r) {
int m = (l + r) / 2;
if (a[m] < x) {
l = m + 1;
} else {
r = m;
}
}
if (a[l] == x) {
return l;
}
return -1;
}
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
while (q--) {
int x;
cin >> x;
cout << binary_search_any(x) << '\n';
}
return 0;
}