Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

 int pivotIndex(int *arr, int low, int high){  
   int mid;  
   //arr is already sorted  
   if(arr[low] <= arr[high]){  
     return low;  
   }  
   //index for min for two elements  
   if(low + 1 == high){  
     if(arr[low] <= arr[high]){  
       return low;  
     }else{  
       return high;  
     }  
   }else{  
     mid = (low + high) / 2;  
     if(arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]){  
       return mid;  
     }else if(arr[mid] < arr[low]){  
       //right half is sorted  
       return pivotIndex(arr, low, mid - 1);  
     }else{  
       //left half is sorted  
       return pivotIndex(arr, mid + 1, high);  
     }  
   }  
 }  
 int binsrch(int *arr, int key, int low, int high){  
   if(low > high){  
     return -1;  
   }  
   int mid = low + (high - low) / 2;  
   if(arr[mid] == key){  
     return mid;  
   } else if(arr[mid] > key){  
     return binsrch(arr, key, low, mid - 1);  
   } else{  
     return binsrch(arr, key, mid + 1, high);  
   }  
 }  
 int search(int* arr, int n, int key) {  
   int flag = -1;  
   int low = 0, high = n - 1;  
   int pivot = pivotIndex(arr, low, high);  
   printf("%d", pivot);  
   if(pivot == 0){  
     flag = binsrch(arr, key, low, high);  
   } else if(key >= arr[low]){  
     flag = binsrch(arr, key, low, pivot - 1);  
   } else {  
     flag = binsrch(arr, key, pivot, high);  
   }  
   return flag;  
 }