https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
Note: This is the version that “may contain duplicates”, but solution is same as 153.

1. Use binary search:

  1. //12 ms    12.3 MB
  3. class Solution {
  4. public:
  5.     int findMin(vector<int>& nums) {
  6.         if(nums.empty()) return -1;
  8.         return findMin(nums, 0, nums.size()-1);
  9.     }
  11. private: 
  12.     int findMin(vector<int>& nums, int l, int r) {
  13.         if(l == r) 
  14.             return nums[l];
  16.         if(l+1 == r) 
  17.             return min(nums[l], nums[r]);
  19.         //sorted in ascending order, num[l] is minimum
  20.         if(nums[l] < nums[r])
  21.             return nums[l];
  23.         int median = l + (r - l) /2;
  25.         return min(findMin(nums, l, median - 1), findMin(nums, median, r));
  26.     }
  27. };