Problem Description

You are given a sorted array of integers, but the array's length is unknown and cannot be accessed directly. Instead, you have access to an interface called ArrayReader, which provides a method get(index) that returns the value at the given index. If you call get(index) for an index that is out of bounds, it returns a large integer (such as 231 - 1). Your task is to find the index of a given target value in the array. If the target is not present, return -1.

• The array is sorted in ascending order.
• There is exactly one valid answer for each input.
• You cannot use the array's length directly.
• You should minimize the number of calls to get().

Thought Process

The central challenge is that we do not know the array's length, so we cannot perform a classic binary search with fixed boundaries. A brute-force approach would be to call get(i) for every index starting from 0 until we either find the target or hit an out-of-bounds value. However, this approach is inefficient, especially for large arrays.

Since the array is sorted, binary search is the ideal choice for searching efficiently. But first, we need to determine a reasonable upper bound for the search range. We can do this by "exponentially expanding" the search boundaries until we either find a value that is greater than or equal to the target or hit an out-of-bounds value.

Once we have a valid range, we can perform a standard binary search within that range. This two-stage process ensures we do not waste calls and maintain an efficient search.

Solution Approach

• Step 1: Exponential Search to Find Boundaries
  • Start with a small right boundary (e.g., right = 1).
  • Double the right boundary repeatedly (right *= 2) until reader.get(right) is greater than or equal to the target, or until reader.get(right) returns an out-of-bounds value.
  • This ensures that the target, if present, is between left (previous right) and right.
• Step 2: Binary Search Within the Found Boundaries
  • Use standard binary search between left and right.
  • At each step, call reader.get(mid):
    • If the value equals target, return mid.
    • If the value is greater than target or is out-of-bounds, move the right boundary left.
    • If the value is less than target, move the left boundary right.
  • If the target is not found, return -1.

We use exponential search to minimize the number of get() calls needed to discover the valid search interval, and binary search to efficiently find the target within that interval.

Example Walkthrough

Suppose the array is: [-1, 0, 3, 5, 9, 12, 15, 20] (unknown length)
Target: 9

1. Exponential Search:
   • Start: left = 0, right = 1
   • reader.get(1) = 0 < 9 → double right: right = 2
   • reader.get(2) = 3 < 9 → double right: right = 4
   • reader.get(4) = 9 ≥ 9 → stop expanding

   Now, left = 2 (previous right), right = 4

2. Binary Search:
   • mid = (2+4)//2 = 3; reader.get(3) = 5 < 9 → left = 4
   • mid = 4; reader.get(4) = 9 == 9 → found at index 4

The algorithm finds the target efficiently without knowing the array's length.

Time and Space Complexity

• Brute-force Approach:
  • Time Complexity: O(N) (linear scan until target or out-of-bounds)
  • Space Complexity: O(1)
• Optimized Approach (Exponential + Binary Search):
  • Exponential search takes O(log P) calls, where P is the position of the target (since right boundary doubles each time).
  • Binary search within the found range is O(log P) as well.
  • Total Time Complexity: O(log P)
  • Space Complexity: O(1) (no extra space used)

Summary

The key to this problem is handling the unknown array size. By combining exponential search (to find a valid search interval) with binary search (to efficiently locate the target), we achieve a highly efficient solution that minimizes the number of interface calls. This method leverages the sorted property of the array and avoids the pitfalls of linear scanning, making it both elegant and practical for large datasets.

Code Implementation

# Leetcode interface
# class ArrayReader:
#     def get(self, index: int) -> int:

class Solution:
    def search(self, reader: 'ArrayReader', target: int) -> int:
        left, right = 0, 1
        # Exponential search to find range
        while reader.get(right) < target:
            left = right
            right *= 2
        # Binary search in found range
        while left <= right:
            mid = left + (right - left) // 2
            val = reader.get(mid)
            if val == target:
                return mid
            elif val > target or val == 2**31 - 1:
                right = mid - 1
            else:
                left = mid + 1
        return -1
      

/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * class ArrayReader {
 *   public:
 *     int get(int index);
 * };
 */
class Solution {
public:
    int search(ArrayReader& reader, int target) {
        int left = 0, right = 1;
        // Exponential search to find bounds
        while (reader.get(right) < target) {
            left = right;
            right *= 2;
        }
        // Binary search
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = reader.get(mid);
            if (val == target) return mid;
            else if (val > target || val == INT_MAX)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return -1;
    }
};
      

/**
 * // This is ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface ArrayReader {
 *     public int get(int index) {}
 * }
 */
class Solution {
    public int search(ArrayReader reader, int target) {
        int left = 0, right = 1;
        // Exponential search to find bounds
        while (reader.get(right) < target) {
            left = right;
            right *= 2;
        }
        // Binary search
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = reader.get(mid);
            if (val == target) return mid;
            else if (val > target || val == Integer.MAX_VALUE)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return -1;
    }
}
      

/**
 * // This is the ArrayReader's API interface.
 * // function ArrayReader() {
 * //     @param {number} index
 * //     @return {number}
 * //     this.get = function(index) {...}
 * // }
 */
/**
 * @param {ArrayReader} reader
 * @param {number} target
 * @return {number}
 */
var search = function(reader, target) {
    let left = 0, right = 1;
    // Exponential search to find bounds
    while (reader.get(right) < target) {
        left = right;
        right *= 2;
    }
    // Binary search
    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2);
        let val = reader.get(mid);
        if (val === target) return mid;
        else if (val > target || val === 2147483647)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1;
};