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.
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;
}