Sunday 17 July 2016

Minimum In Rotated Sorted Array

/* Minimum In Rotated Array */
Suppose a sorted array A 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).
Find the minimum element.
The array will not contain duplicates.
NOTE 1: Also think about the case when there are duplicates. Does your current solution work? How does the time complexity change?
PROBLEM APPROACH: Find the location of the pivot element from where the element is rotated.
Property of pivot : pivot < next && pivot < previous


 #include<iostream>  
 using namespace std;  
 int pivotIndex(int *arr, int low, int high){  
   //if arr[low] <= arr[high], already sorted  
   if(arr[low] <= arr[high]){  
     return arr[low];  
   }  
   if(low + 1 == high){  
     if(arr[low] <= arr[high]){  
       return arr[low];  
     }else{  
       return arr[high];  
     }  
   }  
   int mid = (low + high) / 2;  
   if(arr[mid] <= arr[mid - 1] && arr[mid] <= arr[mid + 1]){  
     return arr[mid];  
   } else if(arr[mid] >= arr[low]){  
     //left half is sorted  
     return pivotIndex(arr, mid + 1, high);  
   }else{  
     return pivotIndex(arr, low, mid - 1);  
   }  
 }  
 int main(){  
   int arr[] = {5, 6, 7, 8, 2, 3, 4};  
   cout << pivotIndex(arr, 0, sizeof(arr)/sizeof(arr[0]) - 1);  
   return 0;  
 }  
Share:

0 comments:

Post a Comment

Contact Me

Name

Email *

Message *

Popular Posts

Blog Archive