Search in a Sorted Array of Unknown Size

给一个api,输入一个index, 返回元素值, 问怎么用这个api在一个不知道大小(并不是无限大)的已排序的数组上做二叉搜索.

二叉肯定要有右边的大小, 所以问题变成怎么快速找到右边的值, 用二次倍增法找

/**
 * // 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) {
        int i = 0;
        int j = 1;
        while(reader.get(j) != 2147483647){
            j = j << 1;
        }
        while(i <= j) {
            int mid = i + (j - i) / 2;
            if(reader.get(mid) == target){
                return mid;
            }
            else if(reader.get(mid) > target){
                j = mid - 1;
            }else{
                i = mid + 1;
            }
        }
        return -1;
    }
};