0 votes
46 views
in Windows by (3.9k points)
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)

1 Answer

0 votes
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

Share:- Whatsapp Facebook Facebook


Welcome to Developerhelpway Q&A, where you can ask questions and receive answers from other members of the community.

Categories

...