AlgoScope

Exponential Search

Double the probe index until the value passes the target, then binary search the last doubling: O(log i).

Searching, algorithm, intermediate
Index 1 holds 3.active 0-11031427394125156187228279311036114012441349145315probe3 < 9

Search Variants: Doubling to a target near the front

Decision, step 2 of 9

Index 1 holds 3, below 9: double the bound to 2.

How search variants works

Cost

Best
O(1)
Average
O(log i)
Worst
O(log i)
Space
O(1)

i is the target's position.

Taught by the same lesson

Search Variants covers these too, in the same run.