Skip to main content

702. Search in a Sorted Array of Unknown Size

medium

Binary-search a sorted array whose length you don't know. The trick is finding bounds in O(log n) via exponential search before the classic two-pointer phase.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array reader sorted in ascending order, write a function to search target in reader. If target exists, return its index; otherwise return -1. You do not know the length of the array. You can access reader.get(i), which returns reader[i] (0-indexed) or 2147483647 if i is out of the array's boundary.

Constraints

  • 1 <= reader.length <= 10^4
  • -9999 <= reader[i], target <= 9999
  • reader is sorted in ascending order.
  • Calls to reader.get(i) past the end return 2^31 - 1 (a sentinel).

Examples

Example 1

Input
reader = [-1,0,3,5,9,12], target = 9
Output
4

Explanation: 9 exists in reader and its index is 4.

Example 2

Input
reader = [-1,0,3,5,9,12], target = 2
Output
-1

Explanation: 2 does not exist in reader so return -1.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

You can't compute mid = (lo + hi) / 2 without knowing hi. Find a valid upper bound first.

Hint 2

Exponential probe: start lo = 0, hi = 1; while reader.get(hi) < target, set lo = hi and hi *= 2. Stops in O(log n) probes.

Hint 3

When the loop exits, target lies in [lo, hi] (using the sentinel as 'past the end'). Run a normal binary search on that window.

Hint 4

Guard against the sentinel: if reader.get(mid) == 2^31 - 1, treat it as 'too big' and narrow upward.

Solution approach

Reveal approach

Two-phase algorithm. Phase 1 (find bounds): start lo = 0, hi = 1. While reader.get(hi) < target, double the window: lo = hi; hi = hi * 2. Each probe halves the remaining unknown space, so this finishes in O(log n) probes. When the loop exits, the answer lies in [lo, hi] (or doesn't exist at all). Phase 2 (classic binary search): standard inclusive-window binary search over [lo, hi]. Compute mid = lo + (hi - lo) / 2. Read v = reader.get(mid). If v == target, return mid. If v < target (including the sentinel branch — sentinel > target), narrow to lo = mid + 1. Else hi = mid - 1. After the loop, return -1. Total complexity: O(log n) probes in phase 1 + O(log n) in phase 2 = O(log n) time and O(1) space. The interview point of this problem is recognizing that you need exponential search to bootstrap the window before you can binary-search.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • binary-search
  • exponential-search

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon
  • Microsoft
  • Facebook

Practice these live with InterviewChamp.AI

Drill Search in a Sorted Array of Unknown Size and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →