Search in a Sorted Array of Unknown Size

Search in a Sorted Array of Unknown Size

What is this problem about?

The Search in a Sorted Array of Unknown Size interview question gives you a sorted integer array of unknown length accessible only through an API (ArrayReader.get(index) that returns a large sentinel value if the index is out of bounds). Your task is to find the target value and return its index using binary search, without knowing the array length upfront.

Why is this asked in interviews?

Microsoft and Google ask this interactive binary search problem because it tests the ability to adapt binary search to constrained API access — a common scenario in distributed systems, database query engines, and streaming data platforms where the full data size is unknown or expensive to compute. It evaluates both the search strategy and the exponential probe to find the right boundary.

Algorithmic pattern used

The pattern is exponential expansion followed by binary search. First, find the search boundaries: start with left=0, right=1. Double right until reader.get(right) >= target (or hits the sentinel). This gives a range [left, right] that is guaranteed to contain the target if it exists. Then apply standard binary search within this range, treating sentinel values as "too large" and moving left.

Example explanation

Sorted array (unknown size): [1, 3, 5, 7, 11, 14, 18, 25]. Target = 14.

Exponential expansion:

• right=1: get(1)=3 < 14 → expand.
• right=2: get(2)=5 < 14 → expand.
• right=4: get(4)=11 < 14 → expand.
• right=8: get(8)=sentinel ≥ 14 → stop. left=4, right=8.

Binary search in [4, 8]:

• mid=6: get(6)=18 > 14 → right=5.
• mid=4: get(4)=11 < 14 → left=5.
• mid=5: get(5)=14 = target → return 5.

Common mistakes candidates make

• Starting with a fixed right boundary — incorrect if the array is larger than expected.
• Not updating left during expansion — after expansion, left should be the previous right (not 0).
• Treating sentinel values incorrectly — they should behave like ∞ (move binary search left).
• Not handling the case where the target doesn't exist.

Interview preparation tip

For the Search in a Sorted Array of Unknown Size coding problem, the binary search and interactive interview pattern requires two phases: boundary finding and binary search. The key insight is exponential expansion — doubling right until you overshoot. Google interviewers appreciate candidates who explain why exponential expansion gives O(log n) total API calls for the boundary phase, the same asymptotic complexity as the binary search phase.