# LeetCode 702. Search in a Sorted Array of Unknown Size

## Description

https://leetcode.com/problems/search-in-a-sorted-array-of-unknown-size/

This is an interactive problem.

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

• returns the value at the `ith` index (0-indexed) of the secret array (i.e., `secret[i]`), or
• returns `231 - 1` if the `i` is out of the boundary of the array.

You are also given an integer `target`.

Return the index `k` of the hidden array where `secret[k] == target` or return `-1` otherwise.

You must write an algorithm with `O(log n)` runtime complexity.

Example 1:

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

Example 2:

```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 <= 104`
• `-104 <= secret[i], target <= 104`
• `secret` is sorted in a strictly increasing order.

## Python Solution

First to find an index where its value is no less than the target. Then we can use a binary search to find the index of the target.

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

class Solution:
"""
:type target: int
:rtype: int
"""

end = 1

end *= 2

start = 0

while start + 1 < end:

mid = start + (end - start) // 2

return mid
start = mid
else:
end = mid