How binary search works and why it is important algorithm
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 and we want to find the position of a value , i.e. such an index that .
A naive solution is to scan the array:
This works in time.
However, because the array is sorted, we can do much better: use binary search and get time: we maintain an interval which definitely contains the answer (if it exists), repeatedly split it into two halves, and discard the half where the answer cannot be.
We will now describe a standard iterative binary search that returns any index such that , or if is not present.
Initialize the answer range, i.e., the interval where the answer lies (). At the very beginning, .
Then we have two cases:
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 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;
}