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