Binary Search
Find an element in a sorted array by halving the search space each step.
How it works
Binary Search works on the divide and conquer principle. Given a sorted array, it repeatedly divides the search interval in half. If the target value is less than the middle element, it narrows to the lower half; if greater, to the upper half. This continues until the element is found or the interval is empty.
The key requirement is that the input must be sorted. In exchange, you get O(log n) search time — searching 1 billion elements takes at most 30 comparisons.
Complexity
Visualizer
Where it's used in the real world
PostgreSQL / B-tree index
Index range scansPostgreSQL's B-tree indexes use a binary-search-like traversal to locate index entries in O(log n). When you run WHERE id = 42 on an indexed column, the planner descends the B-tree using binary comparisons at each node.
Linux kernel
Searching sorted kernel tablesThe kernel uses binary search (bsearch()) in hot paths like looking up system call tables, IRQ descriptors, and exception tables — all of which are sorted at compile time.
Git
git bisectgit bisect is literally binary search over commit history to find which commit introduced a bug. It halves the suspect range on each good/bad verdict.
Standard Libraries
sort.Search (Go), std::lower_bound (C++), Array.prototype (JS)All major standard libraries ship a binary search implementation because it's the canonical O(log n) lookup over sorted collections.
Implementation
function binarySearch(arr: number[], target: number): number {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1; // not found
}
// Usage
const sorted = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(sorted, 7)); // 3
console.log(binarySearch(sorted, 6)); // -1