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)); } }

## Add a Comment