447. Search in a Big Sorted Array

做题历程：

1. 本题是第一次做，独立解出，大概耗时12分钟

其实说真的，要是没有老师课上讲这道题，我肯定不可能做出来。。虽然难度不高，但是比较难想到。

步骤：

1. 寻找end，从1开始，如果此时的值小于target，则end >>= 1，否则就找到了end
2. 跟14. First Position of Target 一样，用Binary Search解题

代码如下：

/**
 * 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 start = 0;
        int end = 1;
        while (true) {
            int kth = reader->get(end);
            if (kth >= target) {
                break;
            }
            else {
                end *= 2;
            }
        }

        while (start + 1 < end) {
            int middle = start + (end - start) / 2;
            int val = reader->get(middle);
            if (val > target) {
                end = middle - 1;
            }
            else if (val == target) {
                end = middle;
            }
            else {
                start = middle + 1;
            }
        }
        if (reader->get(start) == target) {
            return start;
        }
        if (reader->get(end) == target) {
            return end;
        }
        return -1;
    }
};