We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Search in a Sorted Array of Unknown Size

Number: 786

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a sorted array with unique elements of unknown size, you must find the index of a given target value using the ArrayReader interface. The ArrayReader.get(i) function returns the value at index i or 2^31 - 1 if index i is out-of-bound. The goal is to achieve O(log n) runtime.

Key Insights

  • The array is sorted and has unique elements; hence binary search is applicable.
  • Since the array size is unknown, we need to find a proper search boundary first.
  • Doubling the range until the target is less than ArrayReader.get(bound) is a common trick to handle unknown size.
  • Once a boundary is established where target is within the range, standard binary search is applied.

Space and Time Complexity

Time Complexity: O(log n) because the boundary expansion is logarithmic and binary search within the established range is also logarithmic.
Space Complexity: O(1) because only a constant amount of extra space is used.

Solution

We first determine an upper bound for the binary search. Begin with an index (for example, 1) and keep doubling it until ArrayReader.get(index) returns a value greater than or equal to the target, or 2^31 - 1 indicates out-of-bound. Once the range is determined [low, high], perform a binary search: calculate the mid index, check if ArrayReader.get(mid) equals the target, and adjust the low and high pointers accordingly. Special attention is needed when ArrayReader.get(mid) returns the sentinel value (2^31 - 1), which means the search has gone past the valid portion of the array.

Code Solutions

Below are sample solutions provided in Python, JavaScript, C++, and Java with detailed inline comments.

class Solution:
    def search(self, reader, target):
        # Initialize bounds for exponential search.
        low, high = 0, 1  
        # Exponentially increase the boundary until target is within range.
        while reader.get(high) < target:
            low = high
            high *= 2
        # Perform binary search within the determined boundaries.
        while low <= high:
            mid = low + (high - low) // 2
            value = reader.get(mid)
            # If mid element equals target, return index.
            if value == target:
                return mid
            # If mid element is greater than target or out-of-bound.
            elif value > target:
                high = mid - 1
            else:
                low = mid + 1
        # If target is not found, return -1.
        return -1
← Back to All Questions