Search in a Sorted Infinite Array

Search in a Sorted Infinite Array breaks one assumption you lean on without noticing: that you know how long the array is. Binary search needs a right boundary, but here len(arr) is off the table. The fix is exponential search — grow a window until it traps the target, then binary search inside it.

The slow way first

Without a length, the obvious move is to scan left to right until you reach a value >= target. That is a linear scan — O(n) in the worst case, and on a truly huge array it never finishes in time. Worse, it throws away the one thing the array hands you for free: it is sorted.

The question to ask: how do I find a right boundary for binary search without reading every cell? You want to reach the neighborhood of the target in far fewer than n steps.

The idea: double until you overshoot

Start with a tiny window: lo = 0, hi = 1. While arr[hi] is still smaller than the target, the answer lies further right, so leap: set lo = hi, then double hi. Because hi goes 1, 2, 4, 8, 16, ..., it reaches any index p in only about log p jumps. The moment arr[hi] is at least the target, the answer (if it exists) is trapped inside [lo, hi] — and that bracket is small. Then run a plain binary search on [lo, hi].

The key insight: doubling reaches index p in O(log p) steps, and the bracket it leaves behind has width at most hi - lo, which is also O(p) but halves every binary-search step. We never once use len(arr).

Walk through it

Step through the animation. In Phase 1 the hi pointer jumps 1 -> 2 -> 4 -> 8, dimming each cell it leaves behind, until arr[8] = 25 finally clears the target 21. That leaves the bracket [4, 8]. Phase 2 brings in mid and does a textbook binary search: mid = 6 holds 17 (too small, so lo = 7), then mid = 7 holds 21 — found.

Pseudocode

lo, hi = 0, 1
while arr[hi] < target:        # Phase 1: grow the window
    lo = hi
    hi = hi * 2                # double the right bound
while lo <= hi:                # Phase 2: binary search [lo, hi]
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
return -1

The Python solution

def search(arr, target):
    lo, hi = 0, 1
    while arr[hi] < target:
        lo = hi
        hi *= 2
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

• lo, hi = 0, 1 opens the smallest possible window — just the first two cells.
• The first while is Phase 1: as long as arr[hi] is below the target, slide lo up to hi and double hi. This is the doubling loop the animation highlights.
• After it stops, the target (if present) is guaranteed to sit in [lo, hi], because arr[lo] < target <= arr[hi].
• The second while is an ordinary binary search bounded by that bracket — check mid, then discard the half that cannot contain the target.
• Return mid on a match, or -1 if the bracket is exhausted.

Complexity

Both phases are logarithmic in p, the position of the target, so the whole search is O(log p) time and O(1) extra space. No array length required.

When this pattern shows up

Practice