# Search an element in a sorted and rotated array in java

103 views
Search an element in a sorted and rotated array in java.

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