702. Search in a Sorted Array of Unknown Size.md

702. Search in a Sorted Array of Unknown Size (Medium)

• Two element of binary search. 1. find the range. 2. find the target.
• first find the range by right *= 2 each time. if get(right) > target update right.
• then use binary search to search for the target.

class Solution:
    def search(self, reader, target):
        """
        :type reader: ArrayReader
        :type target: int
        :rtype: int
        """
        left = 0
        right = 1
        while(reader.get(right) < target):
            left = right
            right *= 2
        
        # start binary search
        while(left + 1 < right):
            mid = left + (right - left) // 2
            mid_value = reader.get(mid)
            
            if mid_value > target:
                right = mid
            else:
                left = mid
        
        if reader.get(left) == target:
            return left
        elif reader.get(right) == target:
            return right
        else:
            return -1