loading
loading
loading
loading
Find a value in a sorted list in O(log n) by repeatedly halving the search space.
Binary search only works on sorted data. It compares the target to the middle element — if it matches, done; if the target is smaller, search the left half; if larger, search the right half. Repeat until found or the range is empty.
low = 0, high = n − 1.low ≤ high: compute mid = ⌊(low + high) / 2⌋.arr[mid] == target, return mid.arr[mid] < target, set low = mid + 1.high = mid − 1.function binarySearch(arr, target) {
let low = 0, high = arr.length - 1;
while (low <= high) {
// low + (high - low) / 2 avoids integer overflow
// that (low + high) / 2 can cause in fixed-width ints.
const mid = low + ((high - low) >> 1);
if (arr[mid] === target) return mid;
if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}function binarySearch(arr, target, low = 0, high = arr.length - 1) {
if (low > high) return -1; // empty range → not found
const mid = low + ((high - low) >> 1);
if (arr[mid] === target) return mid;
return arr[mid] < target
? binarySearch(arr, target, mid + 1, high)
: binarySearch(arr, target, low, mid - 1);
}| Binary Search | Linear Search | |
|---|---|---|
| Time (worst) | O(log n) | O(n) |
| Space | O(1) iterative | O(1) |
| Input requirement | Must be sorted | Any order |
| Data structure | Random-access (array) | Any sequence |
| Best for | Large, static, sorted data | Small or unsorted data |
| Weakness | Sorting cost if input is unsorted | Slow on large inputs |
Because the array is sorted, one comparison against the middle element tells you which half the target must be in — so the other half, along with the midpoint, can be discarded. Each step throws away half of what remains, which is exactly why the number of steps is log₂(n).
Computing mid = (low + high) / 2 can overflow when low + high exceeds the maximum integer in fixed-width languages (Java, C, Go). Prefer mid = low + (high - low) / 2, which never adds two large values. JavaScript numbers won't overflow this way, but writing it the safe way builds the right habit.
Use while (low <= high) with high = arr.length - 1. The invariant is: if the target exists, it is always within [low, high]. Dropping the = (low < high) or forgetting mid + 1 / mid - 1 are the two most common causes of missed matches or infinite loops.
Plain binary search returns *some* matching index, not necessarily the first. To find the first or last occurrence, keep searching after a match: on a hit, record it and move high = mid - 1 (lower bound) or low = mid + 1 (upper bound). These bisect_left / bisect_right variants are what libraries expose.
The same halving idea powers search on rotated sorted arrays (decide which half is sorted first), 'binary search on the answer' for optimization problems, and finding roots of monotonic functions. Recognising a monotonic predicate is the real skill — the array is just the simplest case.
State the sorted precondition out loud. Write the overflow-safe mid. Name your invariant before coding. Test the empty array, a single element, the first and last elements, and a value that is absent — these edge cases catch most bugs before the interviewer does.
mid = low + (high-low)/2 avoids overflow · Iterative avoids recursion stack · Returns first match found, not necessarily leftmost · Use bisect_left/bisect_right variants for duplicatesStandard binary search returns any matching index, not necessarily the first or last. Use lower/upper-bound variants if you need a specific occurrence.
Not efficiently — binary search needs O(1) random access to the middle element, which arrays provide and linked lists do not.
Each step halves the remaining search space, so it takes about log₂(n) steps to shrink the range to zero or one element.
Share what clicked for you and see notes from other learners on this topic.
Coming soon