/* 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
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;
}
0 comments:
Post a Comment