# Search in a Sorted Array of Unknown Size

Given an integer array sorted in ascending order, write a function to search`target`in`nums`. If`target`exists, then return its index, otherwise return`-1`.**However, the array size is unknown to you**. You may only access the array using an`ArrayReader` interface, where `ArrayReader.get(k)`returns the element of the array at index`k` (0-indexed).

You may assume all integers in the array are less than `10000`, and if you access the array out of bounds,`ArrayReader.get`will return`2147483647`.

**Example 1:**

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

Output:
 4

Explanation:
 9 exists in 
nums
 and its index is 4
```

**Example 2:**

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

Output:
 -1

Explanation:
 2 does not exist in 
nums
 so return -1
```

**Note:**

1. You may assume that all elements in the array are unique.
2. The value of each element in the array will be in the range`[-9999, 9999]`.

## Analysis

隐含条件是数组下标index最大是`Integer.MAX_VALUE`，最简单的想法就是`right`设为`Integer.MAX_VALUE`，然后进行常规的Binary Search。

更好的方法是利用`reader.get(hi) < target`

```java
int hi = 1;
while (reader.get(hi) < target) {
    hi = hi * 2;
}
int low = hi / 2;
```

这样保持了`reader.get(hi) > target`, `reader.get(low) < target`

## Solution

Binary Search - Template #3 (end = Integer.MAX\_VALUE) - (5 ms, faster than 17.24%)

```java
class Solution {
    public int search(ArrayReader reader, int target) {
        int start = 0, end = Integer.MAX_VALUE;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (target == reader.get(mid)) {
                return mid;
            } else if (target < reader.get(mid)) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        if (reader.get(start) == target) {
            return start;
        } else if (reader.get(end) == target) {
            return end;
        }
        return -1;
    }
}
```

Binary Search - Template #1 (hi = hi \* 2 while val < target)

```java
class Solution {
    public int search(ArrayReader reader, int target) {
        int hi = 1;
        while (reader.get(hi) < target) {
            hi = hi * 2;
        }
        int low = hi / 2;
        while (low <= hi) {
            int mid = low + (hi - low) / 2;
            int val = reader.get(mid);
            if (val == target) {
                return mid;
            } else if ( val > target) {
                hi = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
}
```