Overview
Binary Search is a fast divide-and-conquer algorithm for a sorted array. It repeatedly compares the target with the middle element and discards the half that cannot contain it, halving the search space every step.
Because each comparison eliminates half of the remaining candidates, Binary Search reaches its answer in a logarithmic number of steps — dramatically faster than scanning every element on large inputs.
How Binary Search works
- Set two bounds, low and high, to the first and last indices of the sorted array.
- Compute the middle index and compare its element with the target.
- If it matches, return that index; the search is done.
- If the target is smaller, move high just below the middle; if larger, move low just above it.
- Repeat while low ≤ high; if the bounds cross, the target is absent.
When to use it
- Repeated lookups in a large sorted array, where the O(log n) cost pays off many times over.
- Finding insertion points or boundaries (lower/upper bound) in ordered data.
- As a building block for range queries and other search algorithms on sorted arrays.
Complexity analysis
By halving the range at each step, Binary Search runs in O(log n) time in the average and worst cases, with a best case of O(1) when the middle element is the target. It uses O(1) extra space when written iteratively. The key precondition is that the array must be sorted.
Frequently asked questions
Why must the array be sorted for Binary Search?
The algorithm decides which half to discard by comparing with the middle element. That decision is only valid if order guarantees every element on one side is smaller and every element on the other is larger.
How much faster is Binary Search than Linear Search?
For a million elements, Linear Search may need up to a million comparisons while Binary Search needs about twenty (log₂ of a million). The gap widens as the array grows.