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

``````int hi = 1;
hi = hi * 2;
}
int low = hi / 2;``````

Solution

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

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

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

``````class Solution {
int hi = 1;
hi = hi * 2;
}
int low = hi / 2;
while (low <= hi) {
int mid = low + (hi - low) / 2;