Searching in a sorted and rotated array using Java

In this tutorial, we will see how to search an element in a sorted and rotated array using Java. Here, our challenge is to search the element in such an array in o(log n) time complexity. Also, we cannot use linear search as it will take O(n) time complexity. Hence, we will use a variant of binary search for our purpose.

Java program to search an element in a rotated and sorted array

We will divide the array into two sorted sub-arrays, without the need to find the pivot point( it is the point from where the next element is smaller).

import java.io.*;
public class Main {
 
  public static void main(String[] args)throws IOException {
      BufferedReader ob=new BufferedReader(new InputStreamReader(System.in));
    int arr[]={16,19,21,25,3,5,8,10}; //sample array
    System.out.println("Enter number to be searched");
    int num=Integer.parseInt(ob.readLine());
    System.out.println("Index of element "+num+" : "+findElement(arr,0,arr.length-1,num));
  }
  public  static  int findElement(int[] arr,int low,int high,int num)
  {
    int mid;
    while(low<=high)
    {
      mid=low + ((high - low) / 2);
 
      if(arr[mid]==num)
      {
        return mid;
      }
      if(arr[mid]<=arr[high])
     {
        if(num > arr[mid] && num<=arr[high])
        {
          low=mid+1;
        }
        else
        {
          high=mid-1;
        }
      }
      else
    {
        if(arr[low]<=num && num < arr[mid])
        {
          high=mid-1;
        }
        else
        {
          low=mid+1;
        }
      }
    }
    return -1;
  }
}

We will take the input of the element to be searched from the user and send it as the parameter to our function findElement() that will search and return the index of the element, if the element is not found then it will return -1.

The algorithm that we have used in this program is as follows:

We will compute the middle index i.e low+high/2. After that, we have to check if arr[mid…high] is sorted:

• If number lies between the range, low=mid+1.
• If number does not lie in the range, high=mid-1.

Then, we check if arr[low..mid] is sorted:

• If number lies between the range, high=mid-1..
• If number does not lie in the range,low=mid+1.

Output:

Enter number to be searched 5
Index of element 5 : 5

Also read,
Java program to convert Decimal into Hexadecimal