Binary search
Finds a value in a sorted array by looking at the middle and throwing away the half where it cannot be. Each comparison halves what is left.
- best Ω(1)
- average Θ(log n)
- worst O(log n)
- space O(1)
What do these mean?
- Sorted: in increasing order. Binary search needs this; on unsorted data it gives wrong answers.
- Halving: each comparison throws away half of what is left, the half where the target cannot be.
- log₂ n: how many times n can be halved before 1 is left. For 64 values that is 6, so 7 comparisons at most.
- middle (mid)
- found
- ruled out
- target
Every middle the search could pick; a run is one path down. Levels: 5 = ⌈log₂(24 + 1)⌉, the most comparisons it can need.
Look for 70 among 24 sorted values: the whole array is still in play.
Space: play or pause. Left and right arrows: step. Home and End: jump.
Try this: Pick a target that is not in the array. The search still stops after at most ⌈log₂(n + 1)⌉ comparisons, when lo passes hi.
How it works
Binary search keeps two markers, lo and hi, around the part of the array where the target can still be. It looks at the value in the middle: if that is the target, it is done; if it is smaller, the target can only be to its right, so lo moves past the middle; if it is larger, hi moves before it. Every step halves what is left, so 64 values take at most 7 comparisons and a million at most 20. When lo passes hi, nothing is left: the value is not in the array.
When it is a good choice
Use binary search whenever the data is sorted and you can jump to any position: a word in a sorted list, a version in a release history, git bisect, the spot to insert into a sorted array. On unsorted data it gives wrong answers, and sorting first only pays off if you search many times.