## 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
`i`

index (^{th}**0-indexed**) of the secret array (i.e.,`secret[i]`

), or - returns
`2`

if the^{31}- 1`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 = 9Output:4Explanation:9 exists in secret and its index is 4.

**Example 2:**

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

**Constraints:**

`1 <= secret.length <= 10`

^{4}`-10`

^{4}<= secret[i], target <= 10^{4}`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
# """
#class ArrayReader:
# def get(self, index: int) -> int:
class Solution:
def search(self, reader, target):
"""
:type reader: ArrayReader
:type target: int
:rtype: int
"""
end = 1
while reader.get(end) < target:
end *= 2
start = 0
while start + 1 < end:
mid = start + (end - start) // 2
if reader.get(mid) == target:
return mid
elif reader.get(mid) < target:
start = mid
else:
end = mid
if reader.get(start) == target:
return start
if reader.get(end) == target:
return end
return -1
```

- Time Complexity: O(log(T)), where T is the index of the target.
- Space Complexity: O(1).

What is a Shell Script? A shell script is a Linux-based script in which commands are written. When a user executes the script, all the commands tread more , with screen shot and code snipets at

How to Write a Shell Script in Ubuntu