Binary Search
Compare with the middle of a sorted array and half of it stops mattering.
Binary Search: Target on the right
16 is smaller than 56, so 56 can only be to the right. Discard 5 values.
Cost
- Best
- O(1)
- Average
- O(log n)
- Worst
- O(log n)
- Space
- O(1)
Recursive form uses O(log n) stack space.
Before this
Variants
- Lower Bound
- Upper Bound
- First Occurrence
- Last Occurrence
Leads to
Topics that need this one first.