Binary Search on Infinite Arrays
You'll learn how to apply binary search when you don't know the array's size or it's effectively unbounded.
The Challenge
Imagine you have a sorted array so enormous that accessing its length would be too expensive, or it's streaming in dynamically. Traditional binary search requires knowing the endpoints upfront—but what if you don't have that luxury?
The Core Idea
The trick is to find a suitable upper bound first, then apply standard binary search within that range.
Two-phase approach:
-
Exponential search for bounds: Start at index 0 and keep doubling your position (1, 2, 4, 8, 16...) until you find a position where the value is greater than your target (or you hit the end). This gives you a range
[left, right]where your target must live if it exists. -
Standard binary search: Once you've bounded the problem, run regular binary search between
leftandright.
Why Exponential Jumps?
Doubling the position grows exponentially (2⁰, 2¹, 2², 2³...), so you quickly cover vast distances. If the target is at position k, you'll find a suitable upper bound in just O(log k) steps—not O(k) steps!
The Process
Suppose you're searching for target = 50:
- Check index 1, 2, 4, 8, 16... until
arr[16] > 50or you can't read further - Now you know
target(if present) lies between indices 8 and 16 - Apply binary search on that narrow range
Key Takeaway: Binary search on infinite arrays uses exponential probing to find bounds in O(log k) time, then standard binary search, making it efficient even when the array size is unknown or unbounded.