Problem

Given a big sorted array with positive integers sorted by ascending order. 

The array is so big so that you can not get the length of the whole array directly, 

and you can only access the kth number by ArrayReader.get(k) (or ArrayReader->get(k) for C++). 

Find the first index of a target number. 

Your algorithm should be in O(log k), where k is the first index of the target number.

Return -1, if the number doesn't exist in the array.

 Notice

If you accessed an inaccessible index (outside of the array), ArrayReader.get will return 2,147,483,647.

Example
Given [1, 3, 6, 9, 21, ...], and target = 3, return 1.

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

思路

• 因为题目要求log(k) 时间复杂度, 所以用二分法
• 由于二分法需要找到头和尾, 所以需要找到尾位置(于是我卡在这里)
• 其实只需要找到比target要大的位置即可
• 所以每当找到的位置数比target小, 位置 * 2. 那么找尾位置的时间复杂度是 log2( target 位置)
• 然后再用二分

    public int searchBigSortedArray(ArrayReader reader, int target) {
        int lastIndex = 1;
        while (reader.get(lastIndex) < target) {
            lastIndex *= 2;
        }

        int start = 0;
        int end = lastIndex;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (reader.get(mid) >= target) {
                end = mid;
            } else {
                start = mid;
            }
        }

        if (reader.get(start) == target) return start;
        if (reader.get(end) == target) return end;

        return -1;
    }