Search in a Sorted Array of Unknown Size

medium binary search

Problem

Array is hidden behind reader.get(i); return index of target or -1. Out-of-bounds get returns 2^31-1.

Inputarr=[-1,0,3,5,9,12] target=9

Output4

First grow window exponentially, then binary search.

input

def search(reader, target):
    lo, hi = 0, 1
    while reader.get(hi) < target: lo = hi; hi *= 2
    while lo <= hi:
        m = (lo + hi) // 2; v = reader.get(m)
        if v == target: return m
        if v < target: lo = m + 1
        else: hi = m - 1
    return -1

function search(reader, target) {
  let lo = 0, hi = 1;
  while (reader.get(hi) < target) { lo = hi; hi *= 2; }
  while (lo <= hi) {
    const m = (lo + hi) >> 1; const v = reader.get(m);
    if (v === target) return m;
    if (v < target) lo = m + 1; else hi = m - 1;
  }
  return -1;
}

int search(ArrayReader reader, int target) {
    int lo = 0, hi = 1;
    while (reader.get(hi) < target) { lo = hi; hi *= 2; }
    while (lo <= hi) {
        int m = (lo + hi) / 2, v = reader.get(m);
        if (v == target) return m;
        if (v < target) lo = m + 1; else hi = m - 1;
    }
    return -1;
}

int search(const ArrayReader& reader, int target) {
    int lo = 0, hi = 1;
    while (reader.get(hi) < target) { lo = hi; hi *= 2; }
    while (lo <= hi) {
        int m = (lo + hi) / 2, v = reader.get(m);
        if (v == target) return m;
        if (v < target) lo = m + 1; else hi = m - 1;
    }
    return -1;
}

Explanation

We cannot binary search right away because we do not know how long the array is — we can only call reader.get(i), which returns a huge sentinel value for out-of-bounds indices. The fix is to first find a valid right boundary, then binary search as usual.

The first phase grows the window exponentially. Start with hi = 1 and keep doubling it while reader.get(hi) < target, moving lo = hi each time before the jump. Doubling guarantees we pass the target after only about log(position) probes, and the out-of-bounds sentinel safely stops the growth if the target is large.

Once reader.get(hi) >= target, we know the target (if present) lies in [lo, hi], so the second phase is a standard binary search: compute m, read reader.get(m), and move lo or hi based on the comparison, returning m on a match or -1 if the range empties.

Example: arr = [-1,0,3,5,9,12], target 9. Doubling gives hi = 1, 2, 4; at 4, reader.get(4) = 9 >= 9, so we stop with window [0, 4]. Binary search then finds 9 at index 4.

Both phases are logarithmic, so the total work is O(log n) even though the size was unknown at the start.

Time: O(log n) Space: O(1)