Exponential Search
Double the probe index until the value passes the target, then binary search the last doubling: O(log i).
Search Variants: Doubling to a target near the front
Index 1 holds 3, below 9: double the bound to 2.
Cost
- Best
- O(1)
- Average
- O(log i)
- Worst
- O(log i)
- Space
- O(1)
i is the target's position.
Before this
Taught by the same lesson
Search Variants covers these too, in the same run.