```
class Solution {
public:
int search(int a[], int n, int key) {
int pivot = FindPivot(a,n);
if(key == a[pivot])
return pivot;
int index = binary_search(a,0,pivot-1,key);
if(index !=-1)
return index;
return binary_search(a,pivot+1,n-1,key);
}
int FindPivot(int a[], int size) {
int low =1, high= size-1, mid;
if(size ==1)
return 0;
while(low < high)
{
mid = low +(high-low)/2;
if( a[mid-1] <= a[mid] && a[mid] <= a[mid +1]) //in ascending order
low = mid +1;
else if(a[mid-1] >= a[mid] && a[mid] >= a[mid+1])
high = mid -1;
else if(a[mid] > a[mid-1] && a[mid] > a[mid+1])
break;
}
if(high ==0)
low = high;
return low;
}
int binary_search(int a[], const int left, const int right, const int key){
static int index = -1, mid;
if(left > right || left < 0 ) // Error case
return index;
mid = left + (right - left)/2;
if(a[mid] == key)
index = mid;
else if(key < a[mid])
binary_search(a,left,mid-1,key);
else
binary_search(a,mid+1,right, key);
return index;
}
};
```