702.搜索长度未知的有序数组 (Medium)*

/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * class ArrayReader {
 *   public:
 *     int get(int index);
 * };
 */

class Solution {
public:
    int search(const ArrayReader& reader, int target) {
        if(reader.get(0) == target) {
            return 0;
        } 
        int l = 0, r = 1;
        while(reader.get(r) < target) {
            l = r;
            r <<= 1;
        }
        while(l <= r) {
            int mid = l + (r - l) / 2;
            int cur = reader.get(mid);
            if(cur == target) {
                return mid;
            }else if(cur > target) {
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        return -1;
    }
};