Exponential Search and Fibonacci Search Algorithms
- Doubling to find range: 1, 2, 4, 8... until arr[i] >= target. Then binary search in [i//2, min(i, n-1)]. O(log i) where i = target index.
- O(log i) is better than O(log n) when target is near the beginning — for the first 10% of elements, exponential search is 3-4x fewer comparisons.
- Key use case: unbounded/infinite sorted arrays where you cannot start binary search at n//2 because n is unknown.
Exponential search shines in one specific scenario: you have a sorted sequence but do not know its length — or the target is likely near the beginning. Streaming data (real-time sensor readings, log entries), infinite virtual sequences in dynamic programming, or situations where you have prior knowledge that the answer is small.
The doubling-then-binary structure is also the basis for many binary search 'find the boundary' problems: exponential doubling to locate the range, binary search within it. Any time you see 'find the smallest k such that f(k) is true' and you expect k to be small relative to the search space, exponential doubling is the right first move.
Exponential Search
- Start at index 1
- Double: 1, 2, 4, 8, 16... until arr[i] >= target
- Binary search in [i/2, min(i, n-1)]
import bisect def exponential_search(arr: list, target) -> int: n = len(arr) if n == 0: return -1 if arr[0] == target: return 0 # Find range by doubling i = 1 while i < n and arr[i] <= target: i *= 2 # Binary search in [i//2, min(i, n-1)] lo, hi = i // 2, min(i, n - 1) idx = bisect.bisect_left(arr, target, lo, hi + 1) return idx if idx < n and arr[idx] == target else -1 arr = [1,3,5,7,9,11,13,15,17,19,21] print(exponential_search(arr, 7)) # 3 print(exponential_search(arr, 15)) # 7 print(exponential_search(arr, 6)) # -1
7
-1
Unbounded / Infinite Arrays
Exponential search shines when the array is 'infinite' (unknown size or streams).
def search_infinite(stream, target): """Search in a conceptually infinite sorted stream.""" lo, hi = 0, 1 # Expand range until stream[hi] >= target while stream[hi] < target: lo = hi hi *= 2 # Binary search in [lo, hi] while lo <= hi: mid = (lo + hi) // 2 val = stream[mid] if val == target: return mid elif val < target: lo = mid + 1 else: hi = mid - 1 return -1
Fibonacci Search
Fibonacci search uses Fibonacci numbers instead of powers of 2 for range jumps. It avoids division (useful on hardware without division instructions) and has the same O(log n) complexity.
def fibonacci_search(arr: list, target) -> int: n = len(arr) fib2, fib1 = 1, 1 fib = fib2 + fib1 while fib < n: fib2, fib1 = fib1, fib fib = fib2 + fib1 offset = -1 while fib > 1: i = min(offset + fib2, n - 1) if arr[i] < target: fib, fib1, fib2 = fib1, fib2, fib - fib1 offset = i elif arr[i] > target: fib, fib1, fib2 = fib2, fib1 - fib2, fib - fib1 - fib2 else: return i return offset + 1 if fib1 and arr[offset+1] == target else -1 arr = [10,22,35,40,45,50,80,82,85,90,100] print(fibonacci_search(arr, 85)) # 8
Complexity
Exponential Search: O(log i) where i is the target's index — much faster than O(log n) when target is near the start. Fibonacci Search: O(log n) Both use: O(1) space
🎯 Key Takeaways
- Doubling to find range: 1, 2, 4, 8... until arr[i] >= target. Then binary search in [i//2, min(i, n-1)]. O(log i) where i = target index.
- O(log i) is better than O(log n) when target is near the beginning — for the first 10% of elements, exponential search is 3-4x fewer comparisons.
- Key use case: unbounded/infinite sorted arrays where you cannot start binary search at n//2 because n is unknown.
- Fibonacci search: same concept with Fibonacci numbers instead of powers of 2. Avoids division — historically relevant for hardware without division instructions.
- Interview pattern: 'find the boundary' problems (first true in FFFFTTTT) often benefit from exponential doubling to locate the range before binary search.
Interview Questions on This Topic
- QWhy is exponential search useful for infinite arrays?
- QCompare the time complexity of exponential search vs binary search when the target is near index i.
- QWhat is the advantage of Fibonacci search over binary search on certain hardware?
- QHow many range-finding steps does exponential search take to find index i?
Frequently Asked Questions
When would you choose exponential search over binary search?
When the array is unbounded or when you expect the target to be near the beginning. For fixed-size arrays with no prior knowledge of target position, binary search is simpler and equally fast.
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.