702. Search in a Sorted Array of Unknown Size

 T: O(doubling times) = O(logk)
 2^x-2 < k < 2^x-1 => x-2 < logk < x-1 => logk = x, x is doubling times, k is index of result
 
 S: O(1)

use doubling

/**
 * // This is ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface ArrayReader {
 *     public int get(int index) {}
 * }
 
 1-1
 2-1
 4-1
 8-1
 
 
 T: O(doubling times) = O(logk)
 2^x-2 < k < 2^x-1 => x-2 < logk < x-1 => logk = x, x is doubling times, k is index of result
 S: O(1)
 */

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