# 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:

```python
reader.get(index)
```

This returns the value at `index`.

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

```python
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

| Item | Meaning |
|---|---|
| Input | `reader`, an interface for reading array values |
| Input | `target`, the value to search for |
| Output | The index where `target` appears, or `-1` |
| Array property | Sorted in ascending order |
| Out-of-bounds value | `2147483647` |

The function shape is:

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

## Examples

Example 1:

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

The value `9` appears at index `4`.

So the answer is:

```python
4
```

Example 2:

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

The value `2` does not appear in the array.

So the answer is:

```python
-1
```

## First Thought: Binary Search

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

Normal binary search needs two bounds:

```python
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:

```python
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:

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

Stop when:

```python
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:

```python
[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.

| Metric | Value | Why |
|---|---|---|
| Time | `O(log k)` | Boundary doubling takes `O(log k)`, then binary search takes `O(log k)` |
| Space | `O(1)` | Only a few integer variables are used |

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

## Implementation

```python
# """
# 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:

```python
right = 1
```

Then we grow it exponentially:

```python
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:

```python
left = right // 2
```

Then we perform normal binary search:

```python
while left <= right:
```

The middle index is computed safely:

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

Then we read the value through the reader:

```python
value = reader.get(mid)
```

If the value matches, we return the index:

```python
if value == target:
    return mid
```

If the value is too small, search right:

```python
if value < target:
    left = mid + 1
```

Otherwise, search left:

```python
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`.

```python
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:

| Test | Why |
|---|---|
| Target exists in middle | Confirms normal search |
| Target missing | Confirms `-1` case |
| Single element found | Confirms minimum valid array |
| Single element missing | Confirms sentinel behavior |
| Target near end | Confirms boundary expansion |
| Target at index `0` | Confirms left-side boundary behavior |