LeetCode 702: Search in a Sorted Array of Unknown Size

Problem Restatement

We are given a sorted array, but we do not know its length.

We cannot access the array directly. Instead, we can only use an ArrayReader interface:

reader.get(index)

This returns the value at index.

If index is outside the array, reader.get(index) returns a very large sentinel value:

2147483647

We need to find the index of target.

If target exists, return its index.

If it does not exist, return -1.

Input and Output

The function shape is:

class Solution:
    def search(self, reader: "ArrayReader", target: int) -> int:
        ...

Examples

Example 1:

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

The value 9 appears at index 4.

So the answer is:

4

Example 2:

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

The value 2 does not appear in the array.

So the answer is:

-1

First Thought: Binary Search

The array is sorted, so binary search is the natural tool.

Normal binary search needs two bounds:

left = 0
right = len(nums) - 1

But here we do not know len(nums).

So we first need to discover a safe right boundary.

Once we have a range that must contain target if it exists, we can run normal binary search.

Problem With Linear Boundary Search

One simple idea is to check indices one by one:

0, 1, 2, 3, 4, 5, ...

until we find a value greater than or equal to target.

This works, but it may be too slow.

If target is far away, linear scanning takes O(k) calls, where k is the target index.

We want logarithmic behavior.

Key Insight

Instead of growing the right boundary one step at a time, double it.

Check:

1, 2, 4, 8, 16, 32, ...

Stop when:

reader.get(right) >= target

At that point, because the array is sorted, the target cannot be after right.

Also, the previous boundary was right // 2.

So if the target exists, it must be inside:

[right // 2, right]

Then we run binary search inside this interval.

This technique is often called exponential search.

Algorithm

First, find the search boundary.

1. Start with right = 1.
2. While reader.get(right) < target, double right.
3. Set left = right // 2.
4. Run binary search from left to right.

During binary search:

1. Compute mid.
2. Read value = reader.get(mid).
3. If value == target, return mid.
4. If value < target, move left to mid + 1.
5. Otherwise, move right to mid - 1.

The sentinel value 2147483647 works naturally with binary search.

If mid is out of bounds, reader.get(mid) returns a very large value. That value is greater than normal targets, so binary search moves left.

Correctness

The boundary search doubles right until reader.get(right) >= target.

Because the array is sorted, every index greater than or equal to right cannot be needed once this condition holds. If reader.get(right) is an actual array value, then it is at least target. If it is the out-of-bounds sentinel, then right is beyond the real array and all valid indices are before it.

Before the final doubling step, reader.get(right // 2) < target, unless the loop never ran. Therefore, if target exists, it must appear after right // 2 or at right // 2 only in the initial case. Searching the interval [right // 2, right] is therefore sufficient.

The second phase is ordinary binary search on a sorted virtual array. At each step, if the middle value is smaller than target, all indices at or before mid can be discarded. If the middle value is larger than target, or if mid is out of bounds and returns the sentinel, all indices at or after mid can be discarded. If the middle value equals target, the algorithm returns its index.

Thus, if target exists, the algorithm eventually returns its index. If it does not exist, binary search exhausts the valid range and returns -1.

Complexity

Let k be the index of target, or the insertion position where target would belong.

If we express the bound using the hidden array length n, the worst-case time is O(log n).

Implementation

# """
# 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:
        right = 1

        while reader.get(right) < target:
            right *= 2

        left = right // 2

        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

Code Explanation

We begin with a small right boundary:

right = 1

Then we grow it exponentially:

while reader.get(right) < target:
    right *= 2

This loop stops once right points to a value greater than or equal to target, or once right is outside the array and returns the sentinel.

Now the possible range is:

left = right // 2

Then we perform normal binary search:

while left <= right:

The middle index is computed safely:

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

Then we read the value through the reader:

value = reader.get(mid)

If the value matches, we return the index:

if value == target:
    return mid

If the value is too small, search right:

if value < target:
    left = mid + 1

Otherwise, search left:

else:
    right = mid - 1

This also handles out-of-bounds indices because the sentinel value is larger than any normal array value.

Testing

For local testing, we can simulate the ArrayReader.

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

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

def test_search_unknown_size():
    s = Solution()

    reader = ArrayReader([-1, 0, 3, 5, 9, 12])
    assert s.search(reader, 9) == 4

    reader = ArrayReader([-1, 0, 3, 5, 9, 12])
    assert s.search(reader, 2) == -1

    reader = ArrayReader([1])
    assert s.search(reader, 1) == 0

    reader = ArrayReader([1])
    assert s.search(reader, 2) == -1

    reader = ArrayReader([1, 3, 5, 7, 9, 11, 13])
    assert s.search(reader, 13) == 6

    reader = ArrayReader([-10, -5, 0, 4, 8, 15])
    assert s.search(reader, -10) == 0

    print("all tests passed")

Test coverage: