Leetcode 702: Search in a Sorted Array of Unknown Size

The original question can be found here.

The question is asking us to return the index of a target element, however, the size of the array is unknown. The only difference of this question from the traditional binary search question is that the right bound is unknown. From the time complexity requirement, we know that we still need to perform the binary search, so the first task for us is to determine the right bound.

Exponential Backoff

To determine the right bound of the solution domain, we need to peek the element at the right bound to check if it’s no less than target. If yes, we find the solution domain and we can perform the binary search. But how to determine the right range? We first peek the element at index 1 to compare against target. If it’s less than target, we expand the right bound by 2x. For example:

2^0 -> 1      if array[1] < target:
2^1 -> 2      if array[2] < target:
2^2 -> 4      if array[4] < target:
2^3 -> 8      if array[8] < target:
...
2^n           and array[2^n] >= target

We keep expanding the right bound by timing its index by 2. Thus we can use log(k) time to find the right bound, where k is the index of the target elememt.

Code

Now we know the logic for how to find the right bound, it’s time to piece all things together:

class Solution:
    def search(self, reader: 'ArrayReader', target: int) -> int:
        # first find the right bound
        n = 0
        while reader.get(pow(2, n)) < target:
            n += 1
        
        left, right = 0, pow(2, n)
        while left + 1 < right:
            mid = (left + right) // 2
            if reader.get(mid) == target:
                return mid
            elif reader.get(mid) < target:
                left = mid
            else:
                right = mid
        
        if reader.get(left) == target:
            return left
        
        if reader.get(right) == target:
            return right

        return -1

Time complexity: O(n). Space complexity: O(1).