To find an element in an infinite length sorted array in java. See the following code to find an element in an infinite length of sorted array.
package com.dev.search;
public class FindElementInfiniteSizeArray {
public static void main(String[] args) {
int arr[] = {10,20,25,50,70,80};
int x = 70;
boolean isFound = findInfArray(arr, x);
System.out.println("Found: " + isFound);
}
//Time Complexity O(log i)- If the element is present at index i.
//Time Complexity O(logN)- worst case
private static boolean findInfArray(int[] arr, int x) {
if(arr[0]==x) {
return true;
}
int i=1;
while(arr[i] < x) {
i*=2;
if(i>=arr.length) {//data is not present in the array
return false;
}
}
if(arr[i] == x) {
return true;
}else {
return binarySearch(arr, i/2, i, x);
}
}
//Time Complexity O(logN)
private static boolean binarySearch(int[] arr, int l, int h, int x) {
//Corner cases;
if(l>h) {
return false;
}
int mid = (l+h)/2; // mid = l + (h-l)/2;
if(arr[mid] == x) {
return true;
}else if(x > arr[mid]) {
return binarySearch(arr, mid+1, h, x);
}else if(x < arr[mid]) {
return binarySearch(arr, l, mid-1, x);
}
return false;
}
}
Output:- Found: true
