Modified Binary Search

searchInfiniteArray.cpp

int findRight(const ArrayReader& reader, int target){
    int right = 1;
    while (reader.get(right) < target) 
        right = right * 2;
    return right;
}

int searchInfiniteArray(const ArrayReader& reader, int target) {
    int left = 0, right = findRight(reader, target);
     
    while (left <= right){
        int mid = left + (right - left)/2;
        int val = reader.get(mid);
         
        if (val == target) return mid;
        else if (val < target) 
            left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}