Binary Search
Subject: Computer and Technology noun /ˈbaɪ.nə.ri ˌsɜːrtʃ/ 1 definition
- search-algorithms
- divide-and-conquer
- algorithm-design
- computer-science
-
Definition (noun)
Entry #54 · UpdatedBinary Search is a divide-and-conquer search algorithm that finds the position of a target value within a sorted collection by repeatedly halving the remaining search space. At each step, it compares the target against the middle element of the active interval—returning the index on a match, or narrowing the search to either the lower or upper half based on ordering. Because it eliminates half of the remaining candidates per comparison, binary search achieves logarithmic O(log n) worst-case time complexity, though it requires monotonic ordering and constant-time random access such as an array rather than a linked list.
Common Forms
Iterative Binary Search: Uses a loop with
lowandhighindex pointers to narrow the bounds in place, running in O(1) auxiliary memory without call-stack overhead.Recursive Binary Search: Invokes itself on the selected sub-interval until the target is found or the bounds cross, trading O(log n) stack space for a declarative structure.
Lower- and Upper-Bound Search: Variants (such as C++
std::lower_boundand Pythonbisect_left) that locate the leftmost or rightmost valid boundary index for a value, enabling exact insertion points and range queries when duplicate keys exist.Binary Search on Answer (Parametric Search): Searches across a monotonic range of candidate solutions—testing each midpoint with a feasibility predicate—to solve optimization problems such as minimizing maximum latency or required capacity.
Example
When an analytics service searches a sorted in-memory array of 1,000,000 Unix timestamps for an event at
1763376000, binary search checks the middle entry at index 499,999 first and discards whichever half cannot contain the target. By repeating this midpoint split on the remaining interval, it locates the exact timestamp—or confirms its absence—in at most 20 comparisons instead of scanning up to a million elements linearly.