Find Element in Sorted array of infinite Numbers

Problem Link

find-position-element-sorted-array-infinite-numbers

Problem Statement

You are given a sorted array of infinite numbers and a target element key. The task is to find the position (index) of the target element.

Since the array is infinite, the length is unknown. You cannot use the usual arr.length in your algorithm.

Key Assumption

To simulate an infinite array, we are provided with an interface or method like:

int get(int index);

This method will throw an exception or return a special value (e.g., Integer.MAX_VALUE) if the index is out of bounds.

Example

Input:

arr = [3, 5, 7, 9, 10, 90, 100, 130, 140, 160, 170, ...]
key = 10

Output:

4

Intuition

A binary search cannot be directly applied because the upper bound of the array is unknown.

To solve this:

1. Exponential Search is used to find the range where the key lies.

2. Once the range [low, high] is known, apply binary search within that range.

Approach

1. Initialize the search range:

   • Start with low = 0, high = 1

   • While arr[high] < key, expand the range exponentially:

     low = high
     high = high * 2
     

   • This step ensures the key lies between low and high.

2. Apply binary search between low and high.

Java Code

class InfiniteArray {
    public static int findPosition(int[] arr, int key) {
        int low = 0;
        int high = 1;

        // Expand range exponentially until key lies within range
        while (high < arr.length && arr[high] < key) {
            low = high;
            high = high * 2;

            // Prevent index out of bounds
            if (high >= arr.length) {
                high = arr.length - 1;
                break;
            }
        }

        // Perform binary search within the found range
        return binarySearch(arr, low, high, key);
    }

    private static int binarySearch(int[] arr, int low, int high, int key) {
        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] == key) {
                return mid;
            } else if (arr[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return -1; // Key not found
    }
}

Time and Space Complexity

• Time Complexity:

  • Range expansion: O(log p) where p is the index of the key

  • Binary search: O(log p)

  • Overall: O(log p)

• Space Complexity: O(1)

Dry Run

Input:

arr = [3, 5, 7, 9, 10, 90, 100, 130, 140, 160, 170], key = 10

Step 1: Expand the range

• Start: low = 0, high = 1 → arr[1] = 5 < 10

• Update: low = 1, high = 2 → arr[2] = 7 < 10

• Update: low = 2, high = 4 → arr[4] = 10 = 10 → stop

Step 2: Binary Search in range [2, 4]

• mid = 3 → arr[3] = 9 < 10 → search right

• mid = 4 → arr[4] = 10 → match found

Output: 4

Conclusion

This problem is a textbook case of how to handle infinite data streams or unknown-sized arrays. The combination of exponential range expansion and binary search allows us to maintain the desired O(log p) time complexity even without knowing the full array size.

This technique is especially relevant in systems with unbounded input like search engines or streaming datasets.