# Search an element in a sorted and rotated Array

Given a sorted and rotated array **arr[]** of size **N** and a **key**, the task is to find the key in the array.

**Note:** Find the element in O(logN) time and assume that all the elements are distinct.

**Example:**

Input :arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}, key = 3Output :Found at index 8

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

*Output :**Not found*

*Input :** arr[] = {30, 40, 50, 10, 20}, key = 10 *

*Output :**Found at index 3*

The primary idea to solve the problem is as follows.

The idea is to find the pivot point, divide the array into two sub-arrays and perform a binary search.

The main idea for finding a pivot is –

- For a sorted (in increasing order) and rotated array, the pivot element is the only element for which the next element to it is smaller than it.
- Using binary search based on the above idea, pivot can be found.
- It can be observed that for a search space of indices in range
**[l, r]**where the middle index is**mid**, - If rotation has happened in the left half, then obviously the element at
**l**will be greater than the one at**mid**. - Otherwise the left half will be sorted but the element at
**mid**will be greater than the one at**r**. - After the pivot is found divide the array into two sub-arrays.
- Now the individual sub-arrays are sorted so the element can be searched using Binary Search.

`/* Java program to search an element`

`in a sorted and pivoted array*/`

**class**`Main {`

`/* Searches an element key in a`

`pivoted sorted array arrp[]`

`of size n */`

**static****int**`pivotedBinarySearch(`

**int**`arr[], `

**int**`n,`

**int**`key)`

`{`

**int**`pivot = findPivot(arr, 0, n - 1);`

`// If we didn't find a pivot, then`

`// array is not rotated at all`

**if**`(pivot == -1)`

**return**`binarySearch(arr, 0, n - 1, key);`

`// If we found a pivot, then first`

`// compare with pivot and then`

`// search in two subarrays around pivot`

**if**`(arr[pivot] == key)`

**return**`pivot;`

**if**`(arr[0] <= key)`

**return**`binarySearch(arr, 0, pivot - 1, key);`

**return**`binarySearch(arr, pivot + 1, n - 1, key);`

`}`

`/* Function to get pivot. For array`

`3, 4, 5, 6, 1, 2 it returns`

`3 (index of 6) */`

**static****int**`findPivot(`

**int**`arr[], `

**int**`low, `

**int**`high)`

`{`

`// base cases`

**if**`(high < low)`

**return**`-1;`

**if**`(high == low)`

**return**`low;`

`/* low + (high - low)/2; */`

**int**`mid = (low + high) / 2;`

**if**`(mid < high && 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);`

`}`

`/* Standard Binary Search function */`

**static****int**`binarySearch(`

**int**`arr[], `

**int**`low, `

**int**`high,`

**int**`key)`

`{`

**if**`(high < low)`

**return**`-1;`

`/* low + (high - low)/2; */`

**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);`

`}`

`// main function`

**public****static****void**`main(String args[])`

`{`

`// Let us search 3 in below array`

**int**`arr1[] = { 5, 6, 7, 8, 9, 10, 1, 2, 3`

`};`

**int**`n = arr1.length;`

**int**`key = 3;`

`System.out.println(`

`"Index of the element is : "`

`+ pivotedBinarySearch(arr1, n, key));`

`}`

`}`

**Output**

`Index of the element is : 8`

**Time Complexity:** O(log N) Binary Search requires log n comparisons to find the element.**Space Complexity: **O(1)