154. Find Minimum in Rotated Sorted Array II

The key for this problem is still that the minimum number must fall into the rotated part. However, there are duplicates in the array, so for case nums[mid] == nums[hi] or nums[mid] == nums[lo] we only move upper bound one step backward. Why upper bound? Because we are turning lower bound as the result.

1:  class Solution {  
2:  public:  
3:    int findMin(vector<int>& nums) {  
4:      int lo = 0, hi = nums.size()-1;  
5:      while (lo < hi) {  
6:        int mid = lo + (hi - lo) / 2;  
7:        if (nums[mid] > nums[hi]) lo = mid + 1;  
8:        else if (nums[mid] < nums[lo]) hi = mid;  
9:        else hi--;  
10:      }  
11:      return nums[lo];  
12:    }  
13:  };