Binary Search (recursive view)
Each call probes the middle and recurses into the half that can still hold the target. Depth O(log n).
Search Variants: Binary search as a call stack
16 is below 72, so the answer can only be to the right: search 5 to 9. That is a new call on top of this one.
Cost
- Best
- O(1)
- Average
- O(log n)
- Worst
- O(log n)
- Space
- O(log n)
Before this
A variant of
Taught by the same lesson
Search Variants covers these too, in the same run.