LC 0702 [M] Search in a Sorted Array of Unknown Size - ALawliet/algorithms GitHub Wiki

# """
# This is ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
#class ArrayReader:
#    def get(self, index: int) -> int:

class Solution:
    def search(self, reader, target):
        """
        :type reader: ArrayReader
        :type target: int
        :rtype: int
        """
        l, r = 0, 1

        # grow our search space until it's long enough (end index value >= target)
        while reader.get(r) < target:
            l2 = r + 1
            r += (r - l + 1) * 2
            l = l2
        
        while l <= r:
            m = (l + r) // 2
            if reader.get(m) == target:
                return m
            elif reader.get(m) < target:
                l = m + 1
            elif reader.get(m) > target:
                r = m - 1
            
        return -1