Thursday, 7 June 2018

Find an element in a sorted rotated array


public class FindElementInSortedRotatedArray {

    public static void main(String[] args) {
        int findValue = 98;
        int[] arr = {25,35,45,65,67,78,97,98,2,3,4,7,11,22,23,24};
            boolean bool = checkArrIsRotated(arr);
             if(bool) {
                 int index = findPivot(arr);
                 if(findValue>=arr[0] && findValue<=arr[index]) {
                     //first half
                System.out.println(binarySearch(arr, 0, index, findValue));
                 }else {
                     //second half
                System.out.println(binarySearch(arr, index+1, arr.length-1, findValue));
                 }
             }else {
                 //no rotated arr
                 System.out.println(binarySearch(arr, 0, arr.length-1, findValue));
             }
    }
   
    public static int binarySearch(int[] arr,int start,int end,int findValue) {
       
        int mid = 0;
        while(start<=end) {
            mid = (start+end)/2;
            if(arr[mid]==findValue) {
                return mid;
            }else if(findValue<arr[mid]) {
                end = mid-1;
            }else {
                start = mid+1;
            }
        }
        return -1;
    }
   
    public static int findPivot(int[] arr) {
        int start = 0;
        int end = arr.length-1;
        int mid = 0;
        while(start<=end) {
            mid = (start+end)/2;
            if(arr[mid]>arr[mid+1]) {
                return mid;
            }else if(arr[start]<arr[mid]) {
                start = mid+1;
            }else if(arr[start]>arr[mid]) {
                end = mid-1;
            }
        }
        return -1;
    }
   
    public static boolean checkArrIsRotated(int[] arr){
        if(arr[0]>arr[arr.length-1]) {
            return true;
        }
        return false;
       
    }
}

No comments:

Post a Comment

links for Data Structure

  1) 𝐁𝐞𝐜𝐨𝐦𝐞 𝐌𝐚𝐬𝐭𝐞𝐫 𝐢𝐧 𝐋𝐢𝐧𝐤𝐞𝐝 𝐋𝐢𝐬𝐭:  https://lnkd.in/gXQux4zj 2) 𝐀𝐥𝐥 𝐭𝐲𝐩𝐞𝐬 𝐨𝐟 𝐓𝐫𝐞𝐞 𝐓𝐫𝐚𝐯𝐞𝐫𝐬𝐚𝐥𝐬...