Overview
Exponential Search is useful for sorted arrays when the target may be near the front or the size is not known up front.
CoreSource checked
Exponential Search
Finds a search range by doubling the bound, then uses binary search inside it.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Searching
- Difficulty
- Intermediate
- Family
- Range Expansion Search
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Galloping Search
Core Concepts
candidate searchsorted search spacedivide and conquerrange expansion searchcandidate spacematch testsearch interval
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(log i)
Worst
O(log n)
Space
O(1)
When to Use
- Use Exponential Search when you need to expand an upper bound exponentially.
- Use it when the input assumptions match the method's model.
- Use it when you need a clear lookup strategy for known input organization.
- Use it when the method's tradeoffs fit the workload.
When Not to Use
- Avoid it when the input cannot be kept sorted cheaply.
- Avoid it when maintaining the required data layout costs more than the lookup saves.
- Do not treat the O(log i) average case as a guarantee; check the O(log n) worst case.
- Avoid it when the required output is not index of target.
What It Does
- Expands an upper bound exponentially
- Runs binary search inside the discovered range
Use Cases
- Searching unbounded sorted lists
- Finding early targets quickly
- Hybrid sorted-array lookup
Inputs
- Sorted array or stream-like list
- Target value
Outputs
- Index of target
- Not-found result
Pseudocode
- 1.Check the first item
- 2.Double the bound until it reaches or passes the target
- 3.Clamp the bound to the input length
- 4.Binary search between the previous and current bounds
Canonical Example
- Input
- values = [2, 5, 8, 12, 16], target = 12
- Output
- index = 3
- Explanation
- Exponential Search: The search checks candidate positions until it identifies the target value.
Implementation Notes
- Keep the input contract explicit: Sorted array or stream-like list; Target value.
- Decide up front whether not-found results return null, -1, false, or an insertion position.
- Search algorithms should define both success and failure semantics.
Common Pitfalls
- The average cost is often described in terms of the target position i.
- Handle empty, invalid, and boundary inputs before trusting index of target.
- Off-by-one bounds, duplicates, and missing-target behavior should be specified before implementation.
Interactive Mechanism Walkthrough
Indexed Interval & Boundary ProbeShow the search window doubling before a binary search begins.
Target key: 41low=0, mid=4, high=9
4[0]
9[1]
15[2]
22[3]
27[4]
34[5]
41[6]
49[7]
58[8]
63[9]
Step 1 of 4: Check the first item
expanding-rangeNotes
Exponential Search operates in O(log i) time and O(1) space within the Range Expansion Search family. Often compared with Binary Search and Fibonacci Search.
Sources (1)
What each reference supports for this entry.
The Art of Computer Programming, Volume 3
BookSearching reference for Exponential Search's probe strategy, comparison model, and expected or worst-case behavior.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageUsesBinary Search
Exponential search first brackets the target range and then applies binary search within it.
Related Algorithms
Tags
SearchSorted DataDivide and Conquer