Binary search
Efficient search algorithm for sorted arrays.
Binary search is an algorithm used in computing to locate a specific value inside a sorted array. It is sometimes called half-interval search, logarithmic search, or binary chop. The algorithm works by taking the middle element of the array and comparing it to the target. If the two don’t match, the half of the array where the target cannot exist is discarded, and the search repeats on the remaining half. This process continues until the target is found or the remaining half becomes empty, which means the target is not present. In the worst case, binary search operates in logarithmic time, making O(log n) comparisons, where n is the total number of elements. For all but very small arrays, it outperforms linear search, but the array must be sorted beforehand. While specialized structures like hash tables can be searched faster, binary search handles a broader set of problems—for instance, it can find the next-smallest or next-largest element relative to the target even when the target itself is missing. Many variations exist. Fractional cascading speeds up searches for the same value across multiple arrays, which helps in computational geometry and other fields. Exponential search adapts the method for unbounded lists. Data structures such as binary search trees and B-trees are built on the same principle. The algorithm itself starts by comparing the target to the array’s middle element. If they match, the position is returned. If the target is smaller, the search moves to the lower half; if larger, it moves to the upper half. Each iteration eliminates the half where the target cannot be. A common iterative procedure uses two variables, L and R, to track the search boundaries. It sets L to 0 and R to n−1, then repeatedly calculates m as L plus the floor of (R−L)/2. If A[m] is less than T, L becomes m+1; if greater, R becomes m−1; otherwise, m is returned. If the loop ends without a match, the search fails. An alternative version, first published by Hermann Bottenbruch in 1962, skips the equality check in each iteration, only checking when one element remains. This version uses the ceiling of (R−L)/2 for m, and the loop continues while L does not equal R. After the loop, it checks if A[L] equals T. When duplicates exist, the standard procedure may return any matching index, not necessarily the first or last. For finding the leftmost duplicate, a different procedure sets L to 0 and R to n, then uses the floor of (R−L)/2 for m. If A[m] is less than T, L becomes m+1; otherwise, R becomes m. After the loop, L is the leftmost index of T, or the rank of T (the number of elements smaller than T) if T is absent. A similar approach can find the rightmost element. Binary search can also be adapted for approximate matches, such as finding the rank, predecessor, or successor of a value.
- field
- Computer science
- known_for
- Search algorithm that finds the position of a target value within a sorted array
- time_complexity
- O(log n) in the worst case
- data_structure_requirement
- Sorted array
Lore & Background
Binary search operates on sorted arrays by repeatedly dividing the search interval in half. It begins by comparing the target value to the middle element of the array. If they match, the element's position is returned. If the target is smaller, the search continues in the lower half; if larger, in the upper half. This process eliminates the half where the target cannot exist in each iteration, repeating until the target is found or the remaining half becomes empty, indicating the target is absent. The algorithm runs in logarithmic time in the worst case, making it faster than linear search except for very small arrays, though the array must be sorted beforehand. Specialized structures like hash tables can be searched more efficiently, but binary search handles a wider range of problems, such as finding the next-smallest or next-largest element relative to a target even when the target is absent. Numerous variations exist: fractional cascading speeds up searches for the same value across multiple arrays, exponential search extends binary search to unbounded lists, and binary search trees and B-trees are based on its principles. The first implementation to omit the equality check during each iteration was published in 1962 by Hermann Bottenbruch. For arrays with duplicate elements, the standard procedure may return any matching index, but specialized procedures can find the leftmost or rightmost occurrence of the target value.
Reader's Guide
Binary search is significant because it runs in logarithmic time, making it faster than linear search except for small arrays. However, the array must be sorted first to apply binary search. There are specialized data structures like hash tables that can be searched more efficiently, but binary search can solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent. Variations include fractional cascading, which speeds up binary searches for the same value in multiple arrays, and exponential search, which extends binary search to unbounded lists. The binary search tree and B-tree data structures are based on binary search. Hermann Bottenbruch published the first implementation that leaves out the equality check during each iteration, resulting in a faster comparison loop.
Did You Know?
- Binary search is also known as half-interval search, logarithmic search, or binary chop.
- The algorithm eliminates the half in which the target value cannot lie in each iteration.
- Fractional cascading speeds up binary searches for the same value in multiple arrays.
The Halving Principle
Binary search operates on a deceptively simple idea: by always examining the center of a sorted collection, you can discard half of the remaining candidates with every single comparison. The algorithm begins by positioning two boundary pointers, one at the start of the array and one at the end. It then calculates the midpoint, compares that element against the target value, and immediately throws away whichever half cannot possibly contain the answer. If the middle element is too small, the search shifts to the upper half; if too large, it retreats to the lower half. This elimination loop repeats, each iteration shrinking the search space by exactly half, until either the target is located or the remaining interval collapses to zero elements, signaling that the value simply does not exist in the array. The entire procedure is iterative, tracking only two variables, L and R, to maintain the active search window, making it both elegant and straightforward to implement without recursion.
Logarithmic Speed and Its Prerequisites
The defining performance characteristic of binary search is its logarithmic time complexity. In the worst case, the algorithm performs O(log n) comparisons, where n represents the total number of elements in the array. This means that even for arrays containing millions of entries, the search requires only a handful of steps, each one cutting the problem in half. For large datasets, this makes binary search dramatically faster than a linear scan, which must check elements one by one. However, this speed advantage only materializes once the array has already been sorted; the prerequisite of a pre-sorted sequence is the algorithm's most significant constraint. Additionally, for very small arrays, the overhead of computing midpoints and managing boundaries can make a simple linear search competitive or even preferable. And while specialized structures like hash tables can outperform binary search for exact-match lookups, binary search retains a broader utility that hash-based approaches do not always offer.
Beyond Exact Matches
One of binary search's most underappreciated strengths is its ability to solve problems that go well beyond locating an exact value. Even when the target is absent from the array, the algorithm naturally identifies the next-smallest or next-largest element relative to the target, making it a versatile tool for boundary-finding and approximate tasks. This generality sets it apart from lookup structures designed solely for exact matching, such as hash tables, which can outperform binary search for direct lookups but lack this broader problem-solving flexibility. The halving logic also serves as the conceptual foundation for several important data structures: binary search trees and B-trees both rely on the same principle of comparing against a central value and routing the search into the appropriate branch. These structures build upon the compare-and-eliminate principle, extending it into more complex organizational forms that support efficient searching in contexts where a single flat sorted array is insufficient.
Variations and Specialized Extensions
The core halving strategy of binary search has inspired a family of specialized variants tailored to different problem contexts. Fractional cascading, for instance, accelerates the task of searching for the same target value across multiple sorted arrays simultaneously, a technique that proves particularly powerful in computational geometry and numerous other fields where multi-array queries are common. Exponential search extends the binary search paradigm to unbounded lists, where the array has no known upper limit, by first expanding the search range before applying the standard halving procedure. These extensions demonstrate that the fundamental insight, compare, eliminate half, repeat, is not limited to a single fixed-size sorted array but can be adapted to handle dynamic or unbounded search spaces. Each variation preserves the logarithmic spirit of the original while addressing the specific constraints of its application domain, showing how one elegant principle can branch into a rich ecosystem of tools.
Frequently Asked Questions
Who is Binary search?
Binary search is a search algorithm in the Computer Science field that locates a target value inside a sorted array by repeatedly halving the search space. It is also known by the aliases half-interval search, logarithmic search, and binary chop.
What are Binary search's powers and role?
Its signature move is to compare the target against the middle element, discard the half where the target cannot reside, and repeat on the surviving half. This halving strategy yields a worst-case time complexity of O(log n) comparisons.
How does Binary search's story end?
The run concludes the moment the target matches an element or the remaining interval shrinks to zero, signaling the value is absent. Either way, the process wraps up after at most O(log n) iterations.
Why is Binary search important to the canon?
It is a cornerstone algorithm because it shows how a sorted structure enables lookups far faster than a linear scan. Its O(log n) performance makes it the default choice whenever an efficient search over a sorted array is needed.
What does Binary search need to function?
Its one hard requirement is that the input array be pre-sorted; without that ordering guarantee the halving logic collapses. It operates on a sorted array as its essential data-structure prerequisite.
More in Algorithms And Data Structures 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record