Suppose an array sorted in ascending order 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 may contain duplicates.
Example 1:
Input: [1,3,5] Output: 1
Example 2:
Input: [2,2,2,0,1] Output: 0
1 class Solution {
2 public:
3 int findMin(vector<int>& a) {
4 int low = 0;
5 int high = a.size() -1 ;
6 if(high==0) return a[0];
7 int mid = low + (high - low) / 2;
8 if (a[low]<a[high]) return a[low];
9 while(low<high) {
10 mid = low + (high - low) / 2;
11 if (mid ==low ) break;
12 if(a[low] < a[mid]) { //right is shift
13 if(a[mid]<=a[high]) return a[low];
14 low = mid;
15 } else if (a[low] > a[mid]) { //left is shift
16 high = mid;
17 } else {
18 low++;
19 }
20 }
21 return a[low+1];
22 }
23 };