Binary Search
Checks the middle of a sorted array and discards the half that can't hold the target until it finds it or runs out of values.
SearchingDivide and conquerSorted inputO(log n)
How it works
Binary search only works on a sorted array. It keeps a range, low to high, where the target can still be, starting with the whole array. Each step it checks the value in the middle of the range:
- If it equals the target, it returns that index.
- If it is smaller than the target, the target can only be to its right, so the range moves past the middle (
low = mid + 1). - If it is larger, the target can only be to its left (
high = mid - 1).
Every check halves the range. When the range is empty (low > high), the target is not in the array and it returns -1. Because of the halving, even an array of a million values takes at most 20 checks.
When to use it
Binary search is the go-to search for sorted data that you can jump around in by index, especially when you search it many times. If the data isn't sorted and you only search once, a linear search is cheaper than sorting first.
Complexity
| Case | Time | When |
|---|---|---|
| Best | O(1) | The target is the first middle value checked |
| Average | O(log n) | Each check halves the range |
| Worst | O(log n) | The target is found last, or the range runs out |
| Extra space | Why |
|---|---|
| O(1) | It only keeps the low, high and mid indexes |
Implementations
function binarySearch(array, target) {
let low = 0;
let high = array.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
const value = array[mid];
if (value === target) {
return mid;
}
if (value < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
def binary_search(array, target):
low, high = 0, len(array) - 1
while low <= high:
mid = (low + high) // 2
value = array[mid]
if value == target:
return mid
if value < target:
low = mid + 1
else:
high = mid - 1
return -1
#include <vector>
int binarySearch(const std::vector<int>& a, int target) {
int low = 0;
int high = static_cast<int>(a.size()) - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int value = a[mid];
if (value == target) {
return mid;
}
if (value < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}