> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Search in a Sorted Array of Unknown Size

> Tested Python solution for LeetCode 702 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 702, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Binary Search](/catalog/topics/binary-search), [Interactive](/catalog/topics/interactive). [View on LeetCode](https://leetcode.com/problems/search-in-a-sorted-array-of-unknown-size/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 702   # by problem number
lcpy gen -s search_in_a_sorted_array_of_unknown_size   # by problem name
```

## Problem

This is an \<strong>\<em>interactive problem\</em>\</strong>.

You have a sorted array of \<strong>unique\</strong> elements and an \<strong>unknown size\</strong>. You do not have an access to the array but you can use the \<code>ArrayReader\</code> interface to access it. You can call \<code>ArrayReader.get(i)\</code> that:

\<ul>
\<li>returns the value at the \<code>i\<sup>th\</sup>\</code> index (\<strong>0-indexed\</strong>) of the secret array (i.e., \<code>secret\[i]\</code>), or\</li>
\<li>returns \<code>2\<sup>31\</sup> - 1\</code> if the \<code>i\</code> is out of the boundary of the array.\</li>
\</ul>

You are also given an integer \<code>target\</code>.

Return the index \<code>k\</code> of the hidden array where \<code>secret\[k] == target\</code> or return \<code>-1\</code> otherwise.

You must write an algorithm with \<code>O(log n)\</code> runtime complexity.

### Examples

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

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

### Constraints

* `1 <= secret.length <= 10^4`
* `-10^4 <= secret[i], target <= 10^4`
* All the integers of `secret` are \<strong>unique\</strong>.
* `secret` is sorted in a strictly increasing order.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/search_in_a_sorted_array_of_unknown_size/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/search_in_a_sorted_array_of_unknown_size/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class ArrayReader:
    # Test-harness API: backs get() with the hidden sorted array
    def __init__(self, secret: list[int]) -> None:
        self.secret = secret

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


class Solution:
    # Time: O(log M), M = index of the target (bounds doubling then binary search)
    # Space: O(1)
    def search(self, reader: ArrayReader, target: int) -> int:
        # Grow the upper bound exponentially until get(right) >= target;
        # the out-of-bounds sentinel 2^31 - 1 is >= any valid target, so this
        # always terminates. The target, if present, lies in [right // 2, right].
        right = 1
        while reader.get(right) < target:
            right <<= 1
        left = right >> 1
        while left < right:
            mid = (left + right) >> 1
            if reader.get(mid) >= target:
                right = mid
            else:
                left = mid + 1
        return left if reader.get(left) == target else -1
```

## Complexity

| Time | Space |
| - | - |
| O(log M), M = index of the target (bounds doubling then binary search) | O(1) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.