# Find an element in an infinite length sorted array in java?

221 views
in Windows
Find an element in an infinite length sorted array in java?

int arr[] = {10,20,25,50,70,80};

int x = 70;

Output:- true (means found)

by (3.7k points)
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