Finding an Element in an Infinite Array Using Java

Problem Statement

Given an infinite array of sorted integers, we need to find the index of a given target number. The array is "infinite," meaning we cannot determine its size in advance, so we can't just apply a traditional binary search directly.

Approach Overview

1. Start with a small range: Initially, assume that the element lies within a small range (say, between indices 0 and 1).

2. Dynamically increase the range: If the target element is not found in the initial range, we double the size of the range to search further. This exponential growth allows us to quickly hone in on the range where the target might be located.

3. Binary search within the range: Once we determine a suitable range that contains the target, we apply binary search to efficiently find the target's index.

The Code

public class InfiniteArraySearch {
    public static void main(String[] args) {
        // Define the array (for demonstration purposes, treat this as infinite)
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};  
        int target = 6;

        // Call the function to find the target element
        int result = findElementInInfiniteArray(arr, target);
        System.out.println("Element found at index: " + result);
    }

    // Function to find the target in the infinite array
    static int findElementInInfiniteArray(int[] arr, int target) {
        // Start with a small range
        int start = 0;
        int end = 1;

        // Dynamically increase the range until the target is within bounds
        while (target > arr[end]) {
            int newStart = end + 1;  // Update start to one after the current end
            end = end + (end - start + 1) * 2;  // Double the range
            start = newStart;  // Move the start to newStart
        }

        // Perform binary search within the determined range
        return binarySearch(arr, target, start, end);
    }

    // Standard binary search implementation
    static int binarySearch(int[] arr, int target, int start, int end) {
        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (target < arr[mid]) {
                end = mid - 1;  // Move the end to the left
            } else if (target > arr[mid]) {
                start = mid + 1;  // Move the start to the right
            } else {
                return mid;  // Element found
            }
        }
        return -1;  // Element not found
    }
}

Explanation of the Code

1. Main Function

The main function defines an example array arr and a target value 6. For simplicity, we assume the array is finite here, but conceptually, we treat it as infinite. The main function then calls findElementInInfiniteArray to search for the target, and prints the index if found.

2. Range Expansion (Linearly Expanding the Search Area)

In the findElementInInfiniteArray method:

• We begin by assuming that the element lies within the range [0, 1].
• If the target is greater than the value at arr[end], it means the target is not within the current range. So, we expand the range exponentially by doubling it (end = end + (end - start + 1) * 2). This effectively allows us to cover more ground in each iteration.

3. Binary Search

Once we know that the target must lie between start and end, we perform a standard binary search. Binary search is an efficient way to search in sorted arrays, as it reduces the search space by half at each step. The key comparisons are:

• If the target is less than the middle element (arr[mid]), search the left half.
• If the target is greater, search the right half.
• If the target matches the middle element, return its index.

4. Edge Cases

• If the target is smaller than the smallest element in the array, or if the array doesn't contain the target at all, the algorithm will return -1.

Time Complexity

1. Range Expansion: The range doubles with each iteration, so it takes O(log N) operations to find the right range where the target lies.

2. Binary Search: Once the range is found, binary search runs in O(log M), where M is the size of the range.

Thus, the overall time complexity is approximately O(log N + log M).