Search in a Big Sorted Array

Given a big sorted array, 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.

Solution

对于这种大数据的强调，那么一定是有个特殊的方法来返回值，reader.get(),首先得出所有小于target 的最大的索引值。

"""
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):
        index = 0
        while reader.get(index) < target: #第一个索引大于target，这样通过试探的方法可以大大的提高效率。
            index = index * 2 + 1

        start, end = 0, index
        while start + 1 < end:
            mid = (start + end) / 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