702. Search in a Sorted Array of Unknown Size

一刷 05/2022

Time O(logk) -> k is the index of the target number

Space O(1) 

Runtime: 2 ms, faster than 91.48% of Java online submissions for Search in a Sorted Array of Unknown Size.

Memory Usage: 42.9 MB, less than 98.82% of Java online submissions for Search in a Sorted Array of Unknown Size.

/**

 * // This is ArrayReader's API interface.

 * // You should not implement it, or speculate about its implementation

 * interface ArrayReader {

 *     public int get(int index) {}

 * }

 */

class Solution {

    public int search(ArrayReader reader, int target) {

        // Find a upper bound of the range in which we can search for the target

       int end = 1;

        while (reader.get(end) < target) {

            end = end << 1;

        }

        int start = end >> 1;

        while (start <= end) {

            int mid = start + (end - start) / 2;

            if (reader.get(mid) == target) {

                return mid;

            }

            if (reader.get(mid) < target) {

                start = mid + 1;

            } else {

                end = mid - 1;

            }

        }

        return -1;

    }

}