How to find an element in an infinite length sorted array

To solve this problem, we can adopt the following strategy:

1. Determine the Search Range:

   • First, we can search within a small range of the array, starting from index 0 with a fixed step size such as 2^0, 2^1, 2^2, ..., which enables rapid expansion of the search range.
   • For example, we can first check the first element (index 0), then the second (index 1), the fourth (index 3), the eighth (index 7), and so on.
   • Once we identify an element at index i that exceeds the target value, we know the target must lie within the interval (i/2, i].

2. Binary Search:

   • After establishing the potential search range, we can apply a standard binary search within it.
   • During the binary search, we compare the middle element with the target. If the middle element is smaller than the target, we search the right half; if it is larger, we search the left half.

Example

Suppose we want to search for an element x = 22 in an infinitely long sorted array, and we have already determined through step 1 that the target element may reside between indices 3 and 7.

Next, we perform binary search:

1. Check the middle position (e.g., index 5). If the value there is 22, return the index.
2. If the value at index 5 is less than 22, continue searching between indices 6 and 7.
3. If the value at index 5 is greater than 22, continue searching between indices 3 and 4.

This approach effectively locates an element in an infinitely long array without being constrained by its infinite length.

Complexity Analysis

• Time complexity: O(log n), where n is the position of the target element.
• Space complexity: O(1), as no additional space is used.

This solution helps you understand how to search for an element in an infinitely long sorted array.