← Back to the searching page
Jump, Exponential & Interpolation Search
Specialized sorted-array searches: jump ahead in blocks, gallop to find a range, or guess position from value distribution.
What to know
- Exponential search doubles the bound (1, 2, 4, 8…) then binary-searches — ideal for unbounded streams.
- Interpolation search estimates position linearly; O(log log n) on uniform data, O(n) when skewed.
- Galloping is how Timsort merges runs of very different sizes efficiently.
In the wild: Timsort’s merge galloping, phone-book style lookups, sparse index probing.
Algorithms to reach for
Exponential (galloping) search
O(log i)Search unbounded/unknown-length sorted data
Interpolation search
O(log log n) avgUniformly distributed sorted keys
Jump search
O(√n)√n block jumps when binary is awkward
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.