Binary search
Binary search repeatedly checks the midpoint of the remaining range and discards the half that cannot contain the target, halving the search space at every step. It requires the array to be sorted first.
When it is the right choice
Binary search is the right choice whenever the array is already sorted, or will be searched many times, since sorting once and searching repeatedly amortises the cost of the sort. It is the wrong choice for an array that is unsorted and searched only once, where sorting first costs more than a single linear search.
How it works
- Set the low and high boundaries to the first and last position of the array.
- While low has not passed high, find the midpoint of the current range.
- Compare the value at the midpoint with the target.
- If it matches, the target is found.
- If the value at the midpoint is larger than the target, the target must be in the left half, so search there next.
- If the value at the midpoint is smaller than the target, the target must be in the right half, so search there next.
- If the range becomes empty without a match, the target is not in the array.
Worth noticing
- It only works on sorted data — running it on unsorted data can give a wrong answer without any error, since the halving logic silently assumes order.
- Its worst and average case is O(log n), a dramatic improvement over linear search's O(n), but that improvement is only available after paying for the sort.
Cost
- Best
- O(1)
- Average
- O(log n)
- Worst
- O(log n)
- Extra space
- O(1)