# Search in Sorted Rotated Array  Difficulty Level Medium
Array Binary Search Sorting

An element search in sorted rotated array can be found using binary search in O(logn) time. The objective of this post is to find a given element in a sorted rotated array in O(logn) time. Some example of a sorted rotated array is given.

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

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

Input : arr[] = {4,8,16,1,2}
key = 2
Output : Found at index 4```

## Algorithm for Search in Sorted Rotated Array  1. we first find the pivot element, a pivot element is an array element in a sorted rotated array whose both the neighbors (in the array) are less than it. Basically, the pivot is the largest element in an array. pivotSearch() returns the index of pivot.
2. Once the pivot has been found, we perform a binary search range[0,p] or range[p,n-1] depending upon the value of the element to be searched.

here,

p = index of pivot

n = size of the array

```arr[] = {7,8,9,10,1,2,3,5,6}
Element to Search = 2
1.find out pivot p and divide the array into two subarrays range[lo,p] and range[p,hi]
2.perform binary search in one of the subarrays.
a. if key >= arr, call binary search in range[lo,p].
b. else call binary search in range[p,hi]
3.if key is found in selected sub-array then return it's index
else return -1.

lo(index number of first array element) = 0
hi(index number of last array element) = n-1
p = index of pivot
n = size of the array``` ## Implementation  ### C++ Program

```#include <bits/stdc++.h>
using namespace std;

// Standard Binary Search function
int binarySearch(int arr[],int lo,int hi,int key)
{
if (lo <= hi)
{
int mid = (lo+hi)/2; /*low + (high - low)/2;*/

if (key == arr[mid])
return mid;

if (key > arr[mid])
return binarySearch(arr,mid+1,hi,key);

else
return binarySearch(arr,lo,mid-1,key);
}

return -1;  // low > high
}

/* Function to get pivot. For sorted rotated array 7,9,11,12,1,3 it returns 3 (index of 12) */
int pivotSearch(int arr[],int lo,int hi)
{
// base cases
if (hi < lo)
return -1;      // if array is not rotated at all
if (hi == lo)
return lo;

int mid = (lo+hi)/2; /*lo + (hi-lo)/2;*/

// pivot is greater than array element to it's right
if (mid < hi && arr[mid] > arr[mid+1])
return mid;
// pivot is greater than array element to it's left
if (mid > lo && arr[mid] < arr[mid-1])
return (mid-1);

if (arr[lo] >= arr[mid])
return pivotSearch(arr,lo,mid-1);   // pivot lies in left half
else
return pivotSearch(arr,mid+1,hi);   // pivot lies in right half

}

int pivotedBinarySearch(int arr[],int n,int key)
{
int pivot = pivotSearch(arr,0,n-1); // obtain the pivot index

// If no pivot is found,then array is not rotated at all
// in this case we perform a simple binary search as array is sorted (but not rotated)
if (pivot == -1)
return binarySearch(arr,0,n-1,key);

// If we found a pivot, then first compare with pivot value
if (arr[pivot] == key)
return pivot;

// else perform binary search in two subarrays around pivot

// if element to be searched is greater than first (0-index) array element
// then searched element lies between indices - 0 and pivot
if (arr <= key)
return binarySearch(arr,0,pivot-1,key);
// else it lies between indices - pivot and n-1
else
return binarySearch(arr,pivot+1,n-1,key);
}

/* Main program to implement above functions */
int main()
{
// element to be searched = 3
int arr[] = {7,8,9,10,1,2,3,5,6};
int n = sizeof(arr)/sizeof(arr);
int search = 2;

cout << "Index of "<<search<<" : "<<pivotedBinarySearch(arr,n,search);

return 0;
}
```
`Index of 2 : 5`

### Java Program

```class sortedRotatedSearch
{
// Standard Binary Search function
static int binarySearch(int arr[],int lo,int hi,int key)
{
if (lo <= hi)
{
int mid = (lo+hi)/2; /*low + (high - low)/2;*/

if (key == arr[mid])
return mid;

if (key > arr[mid])
return binarySearch(arr,mid+1,hi,key);

else
return binarySearch(arr,lo,mid-1,key);
}

return -1;  // low > high
}

/* Function to get pivot. For sorted rotated array 7,9,11,12,1,3 it returns 3 (index of 12) */
static int pivotSearch(int arr[],int lo,int hi)
{
// base cases
if (hi < lo)
return -1;      // if array is not rotated at all
if (hi == lo)
return lo;

int mid = (lo+hi)/2; /*lo + (hi-lo)/2;*/

// pivot is greater than array element to it's right
if (mid < hi && arr[mid] > arr[mid+1])
return mid;
// pivot is greater than array element to it's left
if (mid > lo && arr[mid] < arr[mid-1])
return (mid-1);

if (arr[lo] >= arr[mid])
return pivotSearch(arr,lo,mid-1);   // pivot lies in left half
else
return pivotSearch(arr,mid+1,hi);   // pivot lies in right half

}

// function to search an element in sorted-rotated array
static int pivotedBinarySearch(int arr[],int n,int key)
{
int pivot = pivotSearch(arr,0,n-1); // obtain the pivot index

// If no pivot is found,then array is not rotated at all
// in this case we perform a simple binary search as array is sorted (but not rotated)
if (pivot == -1)
return binarySearch(arr,0,n-1,key);

// If we found a pivot, then first compare with pivot value
if (arr[pivot] == key)
return pivot;

// else perform binary search in two subarrays around pivot

// if element to be searched is greater than first (0-index) array element
// then searched element lies between indices - 0 and pivot
if (arr <= key)
return binarySearch(arr,0,pivot-1,key);
// else it lies between indices - pivot and n-1
else
return binarySearch(arr,pivot+1,n-1,key);
}

// main function to implement above function
public static void main(String args[])
{
// Let us search 3 in below array
int arr[] = {7,8,9,10,1,2,3,5,6};
int n = arr.length;
int key = 2;
System.out.println("Index of "+key+" is : "+ pivotedBinarySearch(arr,n,key));
}
}```
```Index of 2 is : 5
```

## Improvised Solution/Algorithm for Search in Sorted Rotated Array  we can search an element in the sorted-rotated array in a single pass of binary search. The idea is to look for a particular range of sorted array elements in which the searched element can lie. Once such a range is found, we perform a binary search in that range to look for the searched element. Below is the process :

Maximum Product Subarray

assume ‘key’ is the element to be searched.

```1. find mid point of the range [lo,hi] as mid = (lo+hi)/2
2. if arr[mid] == key : return mid.
3. else if range [lo,mid-1] is sorted
a. if arr[lo] <= key <= arr[mid],search for key in range[lo,mid].
b. else recur for range [mid+1,hi].
4. else range[mid+1,hi] must be sorted
a. if arr[mid+1] <= search <= arr[hi],search for key range[mid+1,hi].
b. else recur for range [lo,mid].```

The following are C++ and Java Implementations of the above algorithm.

## Implementation  ### C++ Program

```#include <bits/stdc++.h>
using namespace std;

// Returns index of searched element 'key' in arr[lo,hi] if key is present
// or else returns -1
int find(int arr[],int lo,int hi,int key)
{
if (lo > hi)
return -1;

int mid = (lo+hi)/2;

if (arr[mid] == key)
return mid;

// if arr[lo,mid-1] is sorted
if (arr[lo] <= arr[mid])
{
if (key >= arr[lo] && key <= arr[mid])
return find(arr,lo,mid-1,key);      // check if key lies in range[lo,mid-1]

else
return find(arr,mid+1,hi,key);      // else recur for range[mid+1,hi]
}
// else arr[mid+1,hi] must be sorted
else
{
if (key >= arr[mid] && key <= arr[hi])
return find(arr,mid+1,hi,key);         // check if key lies in range[mid+1,hi]

else
return find(arr,lo,mid-1,key);         // else recur for range[lo,mid-1]
}
}

// Main Program to implement above functions
int main()
{
int arr[] = {7,8,9,10,1,2,3,5,6};
int n = sizeof(arr)/sizeof(arr);
int key = 2;
int i = find(arr, 0, n-1, key);

i != -1 ? cout<<"Index of "<<key<<" : "<<i<<endl : cout<<"Element Not found";
}
```
`Index of 2 : 5`

### Java Program

```class sortedRotatedSearch
{
// Returns index of searched element 'key' in arr[lo,hi] if key is present
// or else returns -1
static int find(int arr[],int lo,int hi,int key)
{
if (lo > hi)
return -1;

int mid = (lo+hi)/2;

if (arr[mid] == key)
return mid;

// if arr[lo,mid-1] is sorted
if (arr[lo] <= arr[mid])
{
if (key >= arr[lo] && key <= arr[mid])
return find(arr,lo,mid-1,key);      // check if key lies in range[lo,mid-1]

else
return find(arr,mid+1,hi,key);      // else recur for range[mid+1,hi]
}
// else arr[mid+1,hi] must be sorted
else
{
if (key >= arr[mid] && key <= arr[hi])
return find(arr,mid+1,hi,key);         // check if key lies in range[mid+1,hi]

else
return find(arr,lo,mid-1,key);         // else recur for range[lo,mid-1]
}
}

// Main Program to implement above functions
public static void main(String args[])
{
int arr[] = {7,8,9,10,1,2,3,5,6};
int n = arr.length;
int key = 2;
int i = find(arr,0,n-1,key);

if (i != -1)
System.out.println("Index of "+key+" : "+i);
else
}
}
```
`Index of 2 : 5`

## Complexity Analysis  1. Time Complexity T(n) = O(logn)
2. Space Complexity A(n) = O(1)