Search an element in a sorted and rotated array using Java

Hi coders!  I am here with a solution to a new problem related to a sorted array. Many of you may have seen a lot of array related problems but this one is a new kind. Here we will learn how to search an element in a sorted and rotated array in Java. We all know that Array is a data structure which stores similar type of data in contiguous memory locations.

How to Search an element in a sorted and rotated array in Java

Generally, if an array is sorted then the best time complexity to search an element is  O(log n) time by binary search. Now to solve this problem there may be different methods but this is a solution which is optimized with the time complexity of  O(log n) time.

We have given a sorted array {1,2,3,6,7,8,9,10}. Suppose this array is rotated  i.e {6, 7, 8, 9, 10, 1, 2, 3 }.

Input : arr[] = {6, 7, 8, 9, 10, 1, 2, 3}

element to be searched = 3

Output: Found at index 7




The method is to find the pivot point then divide the array into two sub-arrays and call binary search.
The idea of finding pivot is – for a sorted and rotated array, pivot element is the only element for which the element to its right and left both are smaller than the pivot. In this example the pivot =10, element to right=9 (smaller) and element to its left=1 (smaller).

Java code for the problem:

public class SortedAndRotated {
  public static int pivotedBinarySearch(int[] arr, int low,int high, int key) {  //binarysearch function for subarray
    int pivot = findPivot(arr, low, high);
    if (pivot == -1)
      return binarySearch(arr, low, high, key);
    if (arr[pivot] == key)
      return pivot;
    if (arr[low] <= key)
      return binarySearch(arr, low, pivot - 1, key);
    return binarySearch(arr, pivot + 1, high, key);

  }

  public static int findPivot(int arr[], int low, int high) {   //function to find pivot element
    if (high < low)
      return -1;
    if (high == low)
      return low;
    int mid = (low + high) / 2;

    if (arr[mid] > arr[mid + 1])
      return mid;
    if (mid > low && arr[mid] < arr[mid - 1])
      return (mid - 1);

    if (arr[low] >= arr[mid])
      return findPivot(arr, low, mid - 1);
    return findPivot(arr, mid + 1, high);
  }

  public static int binarySearch(int[] arr, int low, int high, int key) { //function of binary search

    if (low > high)
      return -1;
    int mid = (low + high) / 2;
    if (key == arr[mid])
      return mid;
    if (key > arr[mid])
      return binarySearch(arr, mid + 1, high, key);
    return binarySearch(arr, low, mid - 1, key);
}
  public static void main(String[] args) {
    int[] inputArr = { 10, 11, 12, 13, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    SortedAndRotated ob2 = new SortedAndRotated(inputArr);
    int result = ob2.pivotedBinarySearch(inputArr, 0,inputArr.length-1, 4);
    if(result==-1)
     System.out.println("element not found");
    else
    System.out.println(" element found at index:" + result);
  }

}

In the above code, there is a function named as findPivot which is defined such as it finds a pivot element that is the only element for which prev and next element to it are smaller than it. It works on divide and conquers approach. Now with the help of pivot element we got the point before and after which the elements are sorted but one is in increasing order and the other is in decreasing order. So we will apply the Binary Search separately for each subarray.

Output :
element found at index: 7

Hence, the time complexity is O(log n) time.

Hope you understand the code.

You may also learn:


Leave a Reply

Your email address will not be published. Required fields are marked *