描述

给一个按照升序排序的正整数数组。这个数组很大以至于你只能通过固定的接口ArrayReader.get(k) 来访问第k个数。(或者C++里是ArrayReader->get(k))，并且你也没有办法得知这个数组有多大。找到给出的整数target第一次出现的位置。你的算法需要在O(logk)的时间复杂度内完成，k为target第一次出现的位置的下标。如果找不到target，返回-1。

注意事项

如果你访问了 ArrayReader 中一个不可访问的下标（比如越界），ArrayReader
会返回 MAXINT = 2,147,483,647。

样例

给出 [1, 3, 6, 9, 21, ...], and target = 3, return 1.
给出 [1, 3, 6, 9, 21, ...], and target = 4, return -1.

挑战

O(log k)的时间复杂度，k是target第一次出现的下标。

思路

仍旧是经典的二分法模板，只不过变形添加了一个接口调用，没办法直接得到数组长度，用一个while循环加倍增即index = index * 2来求数组长度

代码

/**
 * Definition of ArrayReader:
 *
 * class ArrayReader {
 *      // get the number at index, return -1 if index is less than zero
 *      public int get(int index);
 * }
 */
public class Solution {
    public int searchBigSortedArray(ArrayReader reader, int target) {
        int index = 1;
        //注意此处get里面是index - 1;
        while (reader.get(index - 1) < target) {
            index = index * 2;
        }
        int start = 0;
        int end = index - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (reader.get(mid) < target) {
                start = mid;
            }
            /* 题目求的是first index，应该先令end = mid往前判断是否
             * 还有重复元素出现
             */
            if (reader.get(mid) >= target) {
                end = mid;
            }
        }
        
        if (reader.get(start) == target) {
            return start;
        }
        if (reader.get(end) == target) {
            return end;
        }
        return -1;
    }
}

求first位置时最后的检验应该先检查start，求last位置时最后的检查应该先检查last