0 votes
35 views
in Data Structure And Algorithm by (3.9k points)
Search an element in a sorted and rotated array in java.

1 Answer

0 votes
by (3.7k points)

To search an element in a sorted and rotated array in java follow the following steps:-

  • Find Pivot in given array. If pivot is matched with searched element then return true.
  • After that search in two sub-arrays around pivot:-
    • If arr[0] is less than equal to searched element then call to binarySearch(arr, 0, pivot-1, x) function.
    • Otherwise call to binarySearch(arr, pivot+1,arr.length-1, x); function.

See the Following running code of java:-

package com.dev.gcl3.search;

public class FindInSortedAndRotatedArray {

    public static void main(String[] args) {
        int arr[] = {10,20,30,40,5,6,7,8};
        int x = 20;
        boolean isFound = findElementInSortedAndRoted(arr, x);
        System.out.println("Found: " + isFound);
    }

    //Time Complexity O(logN)
    private static boolean findElementInSortedAndRoted(int[] arr, int x) {
        int pivot = getPivot(arr, 0, arr.length-1);
        System.out.println("Pivot:- "+pivot);
        // If we found a pivot and compare with x
        if(arr[pivot] == x) {
            return true;
        }
        //After that search in two sub-arrays around pivot
        if(arr[0] <= x) {
            return binarySearch(arr, 0, pivot-1, x);
        }
        return binarySearch(arr, pivot+1,arr.length-1, x);
    }

    private static boolean binarySearch(int[] arr, int l, int h, int x) {
        if(l>h) {
            return false;
        }
//        int mid = l+(h-l)/2;
        int mid = (l+h)/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;
    }

    private static int getPivot(int[] arr, int l, int h) {
        //Base cases
        if(l>h)
            return -1;
        if(l==h)
            return l;
        int middle = (l+h)/2;
        if(arr[middle] > arr[middle+1]) {
            return middle;
        }
        if(arr[0] > arr[middle]) {//Go to left in array for finding pivot
            return getPivot(arr, l, middle-1);
        }else{//Go to right in array for finding pivot
            return getPivot(arr, middle+1, h);
        }
    }

}

Output:-
Pivot:- 3
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

...