//Algorithm:
//1. gte the index that ArrayReader.get(index）>= target in O(logk)
//2. Binary search the target between 0 and index

/**
 * Definition of ArrayReader:
 * 
 * class ArrayReader {
 * public:
 *     int get(int index) {
 *          // return the number on given index, 
 *          // return -1 if index is less than zero.
 *     }
 * };
 */
class Solution {
public:
    /**
     * @param reader: An instance of ArrayReader.
     * @param target: An integer
     * @return: An integer which is the first index of target.
     */
    int searchBigSortedArray(ArrayReader *reader, int target) {
        // write your code here

        int index = 1;
        while (reader->get(index) < target) {
            index *= 2; 
        }

        int start = 0;
        int end = index;

        while (start + 1 < end) {
            int midIndex = (end - start) / 2 + start;
            int mid = reader->get(midIndex);
            if (mid == target) {
                // We are searching for the FIRST occurence of target, when a mid == target, there might be number == target on its left and so we continue to search the left of midIndex;
                end = midIndex;
            } else if (mid < target) {
                start = midIndex;
            } else {
                end = midIndex;
            }
        }

        if (reader->get(start) == target) {
            return start;
        } else if (reader->get(end) == target) {
            return end;
        } else {
            return -1;
        }
    }
};