Problem statement

https://leetcode.com/problems/search-in-a-sorted-array-of-unknown-size/

Solution

We can do it in two steps: first find size and then perform binary search. Or we can do binary search directly with start index 0 and end index is MAX_INT, where we just imagine that we fill numbers after end with MAX_INT.

Complexity

Time complexity is O(log MAX_INT).

Code

class Solution:
    def search(self, reader, target):
        beg, end = 0, 10001
        while beg < end:
            mid = (beg + end)//2
            x = reader.get(mid)
            if x == target:
                return mid
            elif x < target: 
                beg = mid + 1
            else:
                end = mid

        return -1