# 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) {
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;
}
}
}
}

``````

### 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.