[LeetCode] Find Minimum in Rotated Sorted Array II

Follow up for “Find Minimum in Rotated Sorted Array”:

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array 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.

• 解题思路
  与上一题相比，比较过程多了中间元素和首尾元素相同的情况，在这种情况下需要分别对前半部分和后半部分求最小值。在最坏情况下，时间复杂度为O(n)。

• 实现代码

/*************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/8 18:33
    *  @Status   : Accepted
    *  @Runtime  : 13 ms
*************************************************************/
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int findMin(vector<int> &num) {
        int begin = 0;
        int end = num.size() - 1;
        return find(num, begin, end);
    }

    int find(vector<int> &num, int begin, int end)
    {
        int mid;
        while (begin < end)
        {
            if (num[begin] < num[end]) //表示没有翻转
            {
                return num[begin];
            }

            mid = (begin + end) / 2;
            if (num[mid] > num[end])
            {
                begin = mid + 1;
            }
            else if (num[mid] < num[end])
            {
                end = mid;
            }
            else
            {
                //分别查找两边
                return min(find(num, begin, mid), find(num, mid + 1, end));
            }
        }
        return num[begin];
    }
};