Introduction
Binary search is a fundamental technique used to efficiently find an element or an optimal value when the answer behaves monotonically.
Suppose we have a sorted array
Binary search is a fundamental technique used to efficiently find an element or an optimal value when the answer behaves monotonically.
Suppose we have a sorted array
Solve these problems to reinforce the lesson material:
Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:
and we want to find the position of a value , that is, an index such that
A simple solution is to scan the array from left to right.
This works in time.
However, since the array is sorted, we can do much better. Using binary search, we can solve the problem in time.
The main idea is to maintain an interval that still may contain the answer, repeatedly split it into two halves, and discard the half where the answer cannot be.
We now describe a standard iterative binary search that returns an index such that a[i] = x, or -1 if is not present.
At the beginning, the answer, if it exists, must lie in the interval:
Then we repeat the following process.
The interval contains only one position.
We split the interval into two parts.
Let
Then the interval is divided into:
Now there are two possibilities:
int find_linear(int x) {
for (int i = 1; i <= n; i++) {
if (a[i] == x) {
return i;
}
}
return -1; // if x does not exist in the array
}
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;
}