Search in a Rotated Array in java

Given a sorted and rotated array A of N distinct elements which is rotated at some point, and given an element key. The task is to find the index of the given element key in the array A.

Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).

Input

• The first line contains two integers N and key.
• The second line contains N spaced integers, elements of A.

Constraints

• 1 ≤ N ≤ 10^7
• 0 ≤ A[i] ≤ 10^8
• 1 ≤ key ≤ 10^8

Output

Print the index of the given key in the array. If the key is not present print -1.

Example

Sample Input

9 10
5 6 7 8 9 10 1 2 3

Sample Output

5

Explanation

10 is found at index 5

Solution of Search in a Rotated Array:–

import java.util.*;
import java.lang.*;
import java.io.*;
 
public class Main
  {
    static int BS( int arr[], int key)
    {
          int l = 0, h = arr.length - 1;
 
      while(l <= h )
        {
          int mid = (l + h)/2;
          if(arr[mid] == key) return mid;
 
          //low <------>mid
          else if(arr[l] <= arr[mid]) // checking for the range to be sorted
          {
            if(key >= arr[l] && key <= arr[mid])
            {
              h = mid -1;
            }
            else
            {
              l = mid +1;
            }
          }
             //mid <------>high
            else if(arr[mid] <= arr[h]) // checking for the range to be sorted
            {
              if(key > arr[mid] && key<= arr[h])
              {
                l = mid + 1;
              }
              else
              {
                h = mid - 1;
              }
            }
        }
      return -1;
    }
 
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int key = sc.nextInt();
 
      int arr[] = new int[n];
 
      for(int i=0; i<n; i++)
        arr[i] = sc.nextInt();
 
      System.out.println(BS(arr, key));
 
	}
}