This content originally appeared on DEV Community and was authored by Mostafa Shariare
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
Start with a small range: Initially, assume that the element lies within a small range (say, between indices 0 and 1).
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.
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
Range Expansion: The range doubles with each iteration, so it takes
O(log N)operations to find the right range where the target lies.Binary Search: Once the range is found, binary search runs in
O(log M), whereMis the size of the range.
Thus, the overall time complexity is approximately O(log N + log M).
This content originally appeared on DEV Community and was authored by Mostafa Shariare
Mostafa Shariare | Sciencx (2024-09-11T03:06:13+00:00) Finding an Element in an Infinite Array Using Java. Retrieved from https://www.scien.cx/2024/09/11/finding-an-element-in-an-infinite-array-using-java/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.