LeetCode 702 - Search in a Sorted Array of Unknown Size

LeetCode Problem 702

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Interactive

Solution

Problem Understanding

This problem asks us to search for a target value inside a sorted array, but with an important limitation: we do not know the size of the array, and we cannot access the array directly.

Instead of normal array indexing, we interact with the array through an ArrayReader interface. The only available operation is:

reader.get(index)

This method behaves in one of two ways:

1. If index is valid, it returns the actual value stored at that position.
2. If index is outside the array bounds, it returns 2^31 - 1, which acts as a sentinel value indicating an invalid index.

The goal is to return the index where target appears in the hidden sorted array. If the target does not exist, we return -1.

The key challenge is that traditional binary search requires knowing the search boundaries, specifically the left and right indices. Since the array size is unknown, we cannot initialize binary search with:

left = 0
right = len(array) - 1

Instead, we must first determine a valid search range.

The constraints tell us several important things:

• The array is sorted in strictly increasing order, meaning binary search is applicable.
• Elements are unique, so there are no duplicate values to worry about.
• The required runtime is O(log n), meaning a linear scan is too slow conceptually.
• The sentinel value 2^31 - 1 is guaranteed to be larger than any valid array element because valid values lie in [-10^4, 10^4]. This makes out-of-bounds detection reliable.

Several edge cases are important:

• The target may be smaller than the first element.
• The target may be larger than all elements.
• The target may not exist inside the array.
• The array may contain only one element.
• During searching, we may repeatedly hit out-of-bounds indices, and our logic must handle those safely.

Approaches

Brute Force Approach

A straightforward solution is to start from index 0 and repeatedly call:

reader.get(i)

We continue checking values until one of two things happens:

• We find the target.
• We encounter 2^31 - 1, meaning we went past the array boundary.

Because the array is sorted, we could also stop early if the current value becomes larger than the target.

This approach works because we eventually either find the target or prove it does not exist. However, it requires scanning potentially every element.

Its runtime is O(n), which violates the problem's requirement for O(log n) complexity.

Key Insight for the Optimal Approach

The challenge is not binary search itself, the challenge is finding a valid search interval.

Since the array size is unknown, we can dynamically discover an upper bound using exponential expansion.

We start with a small search window:

[0, 1]

If the target is larger than the value at index 1, we double the right boundary:

[0,1] → [2,4] → [4,8] → [8,16]

Eventually, one of two things happens:

• We encounter a value greater than or equal to the target.
• We hit an out-of-bounds sentinel value (2^31 - 1).

At that point, we know the target, if it exists, must lie inside the discovered interval.

Then we perform a standard binary search inside that range.

This works efficiently because doubling grows exponentially, meaning we find a suitable boundary in O(log n) time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Sequentially scans indices until target or boundary is found
Optimal	O(log n)	O(1)	Uses exponential boundary expansion followed by binary search

Algorithm Walkthrough

Optimal Algorithm

1. Initialize the search boundaries.

Start with:

left = 0
right = 1

Since we do not know the array size, this gives us a small initial window. 2. Expand the search range exponentially.

While the value at right is smaller than the target:

reader.get(right) < target

double the range size:

left = right
right *= 2

This step efficiently finds a region where the target might exist. 3. Perform binary search inside the discovered range.

Once expansion stops, the target must lie between left and right, if it exists.

Run normal binary search:

• Compute the middle index.
• Read the middle value using reader.get(mid).
• If the value equals the target, return the index.
• If the value is smaller than the target, move left boundary.
• Otherwise, move right boundary.

4. Handle out-of-bounds automatically.

Since reader.get(i) returns 2^31 - 1 for invalid indices, binary search naturally treats out-of-bounds values as extremely large numbers.

Therefore:

if value > target:
    right = mid - 1

safely shrinks the search range. 5. Return -1 if the search ends.

If binary search exhausts the interval without finding the target, it does not exist.

Why it works

The algorithm works because exponential expansion guarantees that we eventually find an interval containing the target, if it exists. Since the array is sorted, once reader.get(right) becomes greater than or equal to the target, any valid occurrence of the target must lie between left and right.

Binary search is correct because the sorted order invariant always holds, and out-of-bounds indices behave like infinitely large values, preventing invalid access from breaking the search logic.

Python Solution

# """
# This is ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
# class ArrayReader:
#     def get(self, index: int) -> int:

class Solution:
    def search(self, reader: 'ArrayReader', target: int) -> int:
        left = 0
        right = 1

        # Expand search boundary exponentially
        while reader.get(right) < target:
            left = right
            right *= 2

        # Standard binary search
        while left <= right:
            mid = left + (right - left) // 2
            value = reader.get(mid)

            if value == target:
                return mid

            if value < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1

The implementation follows the algorithm exactly.

The first section discovers an appropriate search interval. Starting from [0,1], the range doubles until the target is no longer larger than the value at right. This guarantees the target, if present, lies inside the interval.

The second section performs a regular binary search. The midpoint value is fetched using reader.get(mid) instead of direct indexing. Since out-of-bounds accesses return a very large sentinel value, they naturally behave like values larger than the target and push the search leftward.

Finally, if no match is found, the function returns -1.

Go Solution

/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * type ArrayReader struct {
 * }
 *
 * func (this *ArrayReader) get(index int) int {}
 */

func search(reader ArrayReader, target int) int {
	left, right := 0, 1

	// Expand search boundary exponentially
	for reader.get(right) < target {
		left = right
		right *= 2
	}

	// Standard binary search
	for left <= right {
		mid := left + (right-left)/2
		value := reader.get(mid)

		if value == target {
			return mid
		}

		if value < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return -1
}

The Go implementation is almost identical to the Python version.

One small implementation detail is midpoint calculation:

mid := left + (right-left)/2

This avoids potential integer overflow, which is considered best practice in binary search implementations.

Since Go does not have nil concerns for this problem and array access is abstracted through ArrayReader, the implementation remains straightforward.

Worked Examples

Example 1

Input

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

Step 1: Expand Range

Iteration	left	right	reader.get(right)	Action
Initial	0	1	0	Expand
1	1	2	3	Expand
2	2	4	9	Stop

We now search in:

[2, 4]

Step 2: Binary Search

left	right	mid	value	Action
2	4	3	5	Move right
4	4	4	9	Found target

Result:

4

Example 2

Input

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

Step 1: Expand Range

Iteration	left	right	reader.get(right)	Action
Initial	0	1	0	Expand
1	1	2	3	Stop

Search range:

[1, 2]

Step 2: Binary Search

left	right	mid	value	Action
1	2	1	0	Move right
2	2	2	3	Move left

Search ends.

Result:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Exponential expansion takes O(log n), binary search also takes O(log n)
Space	O(1)	Only a few variables are used

The boundary expansion phase doubles the search interval each time, meaning it takes logarithmic time to find an upper bound. Once the interval is found, binary search also runs in logarithmic time. Since logarithmic operations add together rather than multiply, the total runtime remains O(log n).

The algorithm uses only a constant number of variables, so extra memory usage is O(1).

Test Cases

INT_MAX = 2**31 - 1

class ArrayReader:
    def __init__(self, arr):
        self.arr = arr

    def get(self, index: int) -> int:
        if 0 <= index < len(self.arr):
            return self.arr[index]
        return INT_MAX

solution = Solution()

assert solution.search(ArrayReader([-1, 0, 3, 5, 9, 12]), 9) == 4  # example 1
assert solution.search(ArrayReader([-1, 0, 3, 5, 9, 12]), 2) == -1  # example 2

assert solution.search(ArrayReader([5]), 5) == 0  # single element match
assert solution.search(ArrayReader([5]), 1) == -1  # single element no match

assert solution.search(ArrayReader([1, 3, 5, 7]), 1) == 0  # first element
assert solution.search(ArrayReader([1, 3, 5, 7]), 7) == 3  # last element

assert solution.search(ArrayReader([1, 3, 5, 7]), 4) == -1  # missing middle element
assert solution.search(ArrayReader([10, 20, 30]), 5) == -1  # target smaller than minimum
assert solution.search(ArrayReader([10, 20, 30]), 40) == -1  # target larger than maximum

assert solution.search(ArrayReader([-10000, -5000, 0, 5000, 10000]), 5000) == 3  # negatives and positives
assert solution.search(ArrayReader(list(range(10000))), 9999) == 9999  # large input stress test

Test	Why
Example 1	Validates normal successful search
Example 2	Validates target absence
Single element match	Tests smallest valid array
Single element no match	Ensures failure case works
First element	Verifies lower boundary
Last element	Verifies upper boundary
Missing middle element	Tests failed binary search
Smaller than minimum	Ensures early rejection works
Larger than maximum	Tests out-of-bounds handling
Negative and positive values	Validates mixed number ranges
Large input	Stress tests logarithmic performance

Edge Cases

Single Element Array

When the array contains only one element, expansion may immediately access an out-of-bounds index. For example:

[5]

with target 5.

Calling reader.get(1) returns 2^31 - 1, which safely stops expansion. Binary search still correctly checks index 0 and returns the answer.

Target Larger Than All Elements

If the target exceeds every array value, exponential expansion may repeatedly go out of bounds. For example:

[1, 2, 3]
target = 100

Eventually, reader.get(right) returns the sentinel value, which is greater than the target. Binary search then safely eliminates invalid regions and returns -1.

Target Smaller Than First Element

If the target is smaller than the first element, expansion stops immediately because even early values exceed the target.

For example:

[10, 20, 30]
target = 5

Binary search quickly narrows down the range and correctly returns -1.

Out-of-Bounds During Binary Search

Binary search may examine indices outside the real array size. Instead of causing errors, the API returns 2^31 - 1.

Since this sentinel value is always larger than valid targets, the algorithm naturally moves left and avoids invalid areas without requiring special boundary checks.