Find the Position of an Element in a Sorted Infinite Array - Java Solution

1. Introduction

This blog post discusses an algorithmic approach to searching for an element in an infinite sorted array, a problem that poses a unique challenge due to the unknown size of the array.

Problem

Given an infinite sorted array or an array of unknown size, find if a given target value is present in the array. The function should return the index of the target if it is present, otherwise return -1.

Example 1:

Input: Array = [2, 5, 7, 9, 10, 12, 15, 16, 18, 20, 24, 28, 32, 35], target = 16

Output: 7

Explanation: The target is present at index '7' in the array.

Example 2:

Input: Array = [2, 5, 7, 9, 10, 12, 15, 16, 18, 20, 24, 28, 32, 35], target = 19

Output: -1

Explanation: The target is not present in the array.

2. Solution Steps

1. Start with a small range and exponentially increase the range until the target is within the range or the end of the array is reached.

2. Once the range is found, apply a binary search in that range to find the target.

3. If found, return the index; otherwise, return -1.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] nums = {2, 5, 7, 9, 10, 12, 15, 16, 18, 20, 24, 28, 32, 35};
        System.out.println("Index of 16: " + findPosition(nums, 16));
        System.out.println("Index of 19: " + findPosition(nums, 19));
    }

    // Method to find position of an element in a sorted infinite array
    public static int findPosition(int[] nums, int target) {
        // Start with a range of 2
        int start = 0;
        int end = 1;

        // Increase the range exponentially
        while (target > nums[end]) {
            int newStart = end + 1;
            end += (end - start + 1) * 2; // Double the range
            start = newStart;
        }

        // Binary search in the identified range
        return binarySearch(nums, target, start, end);
    }

    // Standard binary search algorithm
    private static int binarySearch(int[] nums, int target, int start, int end) {
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1; // Target not found
    }
}

Output:

Index of 16: 7
Index of 19: -1

Explanation:

The findPosition method initially assumes a small range and expands it exponentially until the target value falls within the range. Once the range is determined, a standard binary search is performed within that range. 

For example, for the input array and target 16, the method identifies the correct range and performs a binary search to find that 16 is at index 7. 

For target 19, the method returns -1 as 19 is not present in the array.