702. Search in a Sorted Array of Unknown Size

Practice Search in a Sorted Array of Unknown Size for free on NudgeCode: Medium, Binary Search pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

There is a hidden array of distinct integers sorted in ascending order. You don't know its length. Return the index of target in it, or -1 if target isn't there.

You can only read the array through the ArrayReader interface:

• reader.get(i) returns the element at index i (0-based), or 2147483647 (2^31 - 1) if i is past the end of the array

There is no length(). Your solution should make O(log n) calls, where n is the array's real length. Each test allows at most 50 calls to get; the 51st call fails the test. In the tests reader is shown as the plain array.

Example

reader = [-1,0,3,5,9,12], target = 9  ->  4
reader = [-1,0,3,5,9,12], target = 2  ->  -1

Constraints

• 1 <= array length <= 10^4
• -10^4 <= array[i], target <= 10^4
• The array's values are distinct and sorted in ascending order