Log inSign up
mediumleetcodeNot Started

Find Position of an Element in a Sorted Array of Unknown Size

Given an integer array sorted in ascending order with an unknown size and an ArrayReader interface, find the index of target in O(log T) time.

Binary Search
Solve on leetcode
Lesson

Problem Statement

This is an interactive problem.\n\nYou have a sorted array of unique elements and an ArrayReader interface. You do not know the length of the array.\n\nYou are given an integer target. The interface provides a method reader.get(k) which:\n- Returns the element of the array at index k (0-indexed).\n- Returns 231 - 1 (i.e. 2147483647) if k is out of bounds.\n\nImplement an algorithm that returns the index of target in the array, or -1 if target is not in the array.\n\nYou must write an algorithm with O(log T) runtime complexity, where T is the index of target.

Example 1 · Example 1: Target Present:

Input: array = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Explanation: 9 exists in array and its index is 4.

Example 2 · Example 2: Target Absent:

Input: array = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Explanation: 2 does not exist in array so return -1.

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i], target <= 104
  • All integers in nums are unique and sorted in ascending order.
  • reader.get(k) returns 2147483647 if k is out of bounds.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Interface with restricted/abstract data access APIs (ArrayReader).
  • Use exponential doubling to determine range bounds.
  • Leverage sentinel values gracefully in binary search predicates.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Array length is unknown; accessible via ArrayReader.get(k).
  • Out of bounds returns 231 - 1.
  • Target search in O(log T) time.

Algorithmic Decision Tree:

  • Set low = 0, high = 1.
  • While reader.get(high) < target: low = high, high = high * 2.
  • Binary search within [low, high] using reader.get(mid).

Connected Patterns:

Search in a Sorted Infinite ArrayExponential SearchBinary Search

1. Sequential Reader Query

Intuition

Loop i from 0 upwards. Check reader.get(i). If equal to target, return i; if greater than target or sentinel, return -1.

When to apply: Baseline benchmark.

Algorithm

  1. Step 1: Set i = 0.
  2. Step 2: Read val = reader.get(i).
  3. Step 3: If val == target, return i.
  4. Step 4: If val > target, return -1.
  5. Step 5: i++, repeat.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int search(const ArrayReader& reader, int target) {
8 int i = 0;
9 while (true) {
10 int val = reader.get(i);
11 if (val == target) return i;
12 if (val > target) return -1;
13 i++;
14 }
15}
16
17int main() {
18 // Sample driver execution
19 cout << "Execution completed successfully." << endl;
20 return 0;
21}
22

Time & Space Complexity

  • Time complexity: O(T) — Makes T sequential API queries.
  • Space complexity: O(1) — O(1) memory.

2. Large Upper Bound Binary Search

Intuition

Set low = 0, high = 20000. Run binary search using reader.get(mid). Any out of bounds returns 231 - 1, which correctly moves high to the left.

When to apply: When maximum constraint size is known to be small (e.g., 10000).

Algorithm

  1. Step 1: Set low = 0, high = 20000.
  2. Step 2: While low <= high:
  3. - mid = low + (high - low) / 2.
  4. - val = reader.get(mid).
  5. - If val == target return mid.
  6. - If val < target low = mid + 1, else high = mid - 1.
  7. Step 3: Return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int search(const ArrayReader& reader, int target) {
8 int low = 0, high = 20000;
9 while (low <= high) {
10 int mid = low + (high - low) / 2;
11 int val = reader.get(mid);
12 if (val == target) return mid;
13 if (val < target) low = mid + 1;
14 else high = mid - 1;
15 }
16 return -1;
17}
18
19int main() {
20 // Sample driver execution
21 cout << "Execution completed successfully." << endl;
22 return 0;
23}
24

Time & Space Complexity

  • Time complexity: O(log(MAX_N)) — Takes fixed log2(20000) ~ 15 iterations regardless of how small target index T is.
  • Space complexity: O(1) — O(1) memory.

3. Exponential Doubling + Targeted Binary Search

Intuition

Start with low = 0, high = 1. While reader.get(high) < target, set low = high and high <<= 1 (high * 2). Then binary search within [low, high].

When to apply: Optimal solution requiring minimal API calls adaptive to T.

Algorithm

  1. Step 1: low = 0, high = 1.
  2. Step 2: While reader.get(high) < target: low = high, high = high * 2.
  3. Step 3: While low <= high:
  4. - mid = low + (high - low) / 2.
  5. - val = reader.get(mid).
  6. - If val == target return mid.
  7. - If val < target low = mid + 1, else high = mid - 1.
  8. Step 4: Return -1.

Trace for array = [-1, 0, 3, 5, 9, 12], target = 9

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Step 1: low=0, high=1
Visual state
Values and pointers at this exact step
pointers
S
-1
0
3
5
9
12
0
↑ low
1
↑ high
2
3
4
5
Check / comparison
reader.get(1)=0 < 9 -> Double high
Decision / next transition
Set low=1, high=2
Why this step matters

Step 1: low=0, high=1. reader.get(1)=0 < 9. Double high: low=1, high=2.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int search(const ArrayReader& reader, int target) {
10 int low = 0, high = 1;
11 while (reader.get(high) < target) {
12 low = high;
13 high <<= 1;
14 }
15 while (low <= high) {
16 int mid = low + (high - low) / 2;
17 int val = reader.get(mid);
18 if (val == target) return mid;
19 if (val < target) low = mid + 1;
20 else high = mid - 1;
21 }
22 return -1;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(log T) — Doubling takes log2(T) steps. Binary search takes log2(2T - T) = log2(T) steps. Total time is O(log T).
  • Space complexity: O(1) — Requires O(1) auxiliary space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Sequential QueryO(T)O(1)Query reader index by index.Linear scan.
2.Fixed Max Bound Binary SearchO(log(MAX))O(1)Binary search on max array capacity directly.Fixed search window.
3.Exponential Doubling + Binary SearchOptimalO(log T)O(1)Dynamically double high pointer then binary search.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Target is at index 0.
  • Target is smaller than nums[0] -> returns -1.
  • Target is larger than all elements in nums -> binary search encounters sentinels and returns -1.
  • Array contains only 1 element.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State why linear scanning is suboptimal (O(T) vs O(log T)).
  2. Explain how the sentinel 231 - 1 cleanly acts as infinity, making binary search logic uniform.
  3. Mention that the total number of get() calls is bounded by 2 * log2(T).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is reader.get(k) returning 231 - 1 convenient for binary search?

Back to DSA Sheet