Binary search algorithm
Binary Search Algorithm
The binary search algorithm is a search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half. It is also known as half-interval search, logarithmic search, or binary chop. Binary search runs in O(log n) time, making it much more efficient than linear search for large arrays.
The algorithm works by comparing the target value to the middle element of the array. If they are equal, the position is returned. If the target is less than the middle element, the search continues on the lower half; if greater, on the upper half. This process repeats until the target is found or the interval becomes empty, indicating that the target is not present.
Algorithm
Binary search can be implemented iteratively or recursively. The iterative version uses a loop to adjust the low and high boundaries, while the recursive version calls itself with updated bounds. Both variants maintain the invariant that if the target exists, it lies between the current low and high indices.
Complexity
The worst-case and average-case time complexity is O(log n) comparisons. The best-case is O(1) when the target is the middle element. Space complexity is O(1) for the iterative version and O(log n) for the recursive version due to call stack usage.
History
The concept of binary search was first published in 1946 by John Mauchly, though the first correct implementation of the binary search algorithm did not appear until 1960. Early versions often contained off-by-one errors. The ubiquity of binary search in computer science textbooks and its fundamental role in algorithm design make it a classic example of the divide-and-conquer paradigm.
Variants
- Exponential search – for unbounded or infinite lists.
- Interpolation search – uses probing based on value distribution; best-case O(log log n).
- Ternary search – divides the array into three parts; still O(log n) but with more comparisons per step.