Search in a Big Sorted Array – Python 3 (Week 17 – 16)

class Solution:
    """
    @param: reader: An instance of ArrayReader.
    @param: target: An integer
    @return: An integer which is the first index of target.
    """
    def searchBigSortedArray(self, reader, target):
        # write your code here

    
        start, end = 0, 1
        while reader.get(end) < target:
            end = end * 2 + 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            print(mid)
            if reader.get(mid) < target:
                start = mid
            else:
                end = mid
        if reader.get(start) == target:
            return start
        if reader.get(end) == target:
            return end
            
        return -1

class Solution:
    """
    @param: reader: An instance of ArrayReader.
    @param: target: An integer
    @return: An integer which is the first index of target.
    """
    def searchBigSortedArray(self, reader, target):
        # write your code here
        first = reader.get(0)
        if first == target:
            return 0
        if first > target:
            return -1
            
        index, jump = 0, 1 
        while jump:
            while jump and reader.get(index + jump) >= target:
                jump = jump // 2
            index += jump
            jump *= 2
            
        if reader.get(index + 1) == target:
            return index + 1
        return -1