int search(int* arr, int n, int key) {
int si = 0;
int ei = n-1;
// core concept : if array is rotated and we visited any index then one part
// of array is going to be sorted
while(si <= ei){
int mid = (si + ei)/2;
if(arr[mid] == key){
return mid;
}
if(arr[mid] >= arr[si]){
// if mid == si this means left part has one element and that is sorted
// left array is sorted
if(key < arr[mid] && key >= arr[si]){
ei = mid - 1;
continue;
}else{
si = mid + 1;
}
}
if(arr[mid] <= arr[ei]){
// here arr[mid] can be equal to arr[ei] if there is only one
// element in whole array
// righty array is sorted
//
if(key <= arr[ei] && key > arr[mid]){
si = mid + 1;
}else{
ei = mid - 1;
}
}
}
return -1;
}