702-search-in-a-sorted-array-of-unknown-size

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

You may assume all integers in the array are less than 10000, and if you access the array out of bounds,ArrayReader.getwill return2147483647.

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].

public int search(ArrayReader reader, int target) {
        int right = 0, val = reader.get(right);
        while (val != Integer.MAX_VALUE) {
            if (val < target) {
                right = right == 0 ? 1 : right * 2;
                val = reader.get(right);
            } else {
                break;
            }
        }
        
        int left = right / 2, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            val = reader.get(mid);
            if (val == target) {
                return mid;
            } else if (val < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

what if we don't know the size of array(the search range)?

we will find an approximate one, by double the right index every time untile arr[right] > target

Then do a regular bs