Search in a Big Sorted Array

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 byArrayReader.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.

Example

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

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

这题目其实主要考察个如何“倍增”，二分法的内容其实没啥区别。

首先可以确定的是，倍增到大于target，接下来用二分法找first element。

"""
Definition of ArrayReader:
class ArrayReader:
    def get(self, index):
        # this would return the number on the given index
        # return -1 if index is less than zero.
"""
class Solution:
    # @param {ArrayReader} reader: An instance of ArrayReader 
    # @param {int} target an integer
    # @return {int} an integer
    def searchBigSortedArray(self, reader, target):
        # write your code here
        index = 0
        while reader.get(index) < target:
            index = index * 2 + 1
        start = 0
        end = index
        while start + 1 < end:
            mid = (start+end)/2
            if target > reader.get(mid):
                start = mid
            else:
                end = mid
        if reader.get(start) == target:
            return start
        elif reader.get(end)==target:
            return end
        return -1