There is a sorted array of infinite numbers, write an algorithm to search the element in the array?
Since the array is sorted, the first thing clicks into mind is binary search, but the problem here is that we don’t know the size of the array.
As the array is infinite, that means we don’t have proper bounds to apply binary search. So in order to search the element, first we find bounds and then apply a binary search algorithm.
Let low be pointing to 1st element and high pointing to 2nd element of the array. Now compare key with high index element:
1. If it is greater than the high index element then copies high index in the low index and double the high index.
2. if it is smaller, then apply binary search on high and low indices found.
package com.algorithmforum.array;
public class ElementInInfiniteArray {
/** Simple binary search algorithm .*/
private static int binarySearch(int arr[], int l, int r, int element) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == element) {
return mid;
}
if (arr[mid] > element) {
return binarySearch(arr, l, mid - 1, element);
}
return binarySearch(arr, mid + 1, r, element);
}
return -1;
}
/**
* Method takes an infinite size array and a key to be searched and returns its
* position if found else -1.
* As we don't know the size of array[] and we can assume the size
* to be infinite in this function.
*
* NOTE THAT this function assumes array[] to be
* of infinite size, therefore, there is no index out of bounds checking
*/
private static int findPosition(int array[], int element) {
int l = 0, h = 1;
int val = array[0];
// Find h to do binary search
while (val < element) {
l = h; // store previous high
h = 2 * h; // double high index
val = array[h]; // update new val
}
/** Here, we have updated low and high indices, thus binary search can be applied.*/
return binarySearch(array, l, h, element);
}
// Driver method
public static void main(String[] args) {
int[] array = { 3, 5, 7, 9, 10, 90, 100, 130, 140, 160, 170 };
int index = findPosition(array, 10);
if (index == -1) {
System.out.println("Element not found");
} else {
System.out.println("Element found at index " + index);
}
}
}
Output:
Element found at index 4
Let p be the position of element to be searched. Number of steps for finding high index ‘h’ is O(Log p). The value of ‘h’ must be less than 2*p. The number of elements between h/2 and h must be O(p). Therefore, time complexity of Binary Search step is also O(Log p) and overall time complexity is 2*O(Log p) which is O(Log p).
