leetcode Question: Find Minimum in Rotated Sorted Array II

Find Minimum in Rotated Sorted Array II

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.

The solution is similar to the previous question (here), only difference is we can 'skip' the duplicates before determining if the sub array is ordered.


class Solution {
    void bs(vector<int> &num, int st,int ed, int &res){
        if (st>ed){ return; }
        else {
            int mid = st+(ed-st)/2; //get middle index
            while (num[mid]==num[ed] && mid!=ed) {ed--;}
            while (num[mid]==num[st] && mid!=st) {st++;}
            if (num[mid]<num[ed] || mid==ed){  // right part ordered
                res = min(res,num[mid]); //get right part min
                bs(num,st,mid-1,res); //search left part
            } else {  //right part unordered
                res = min(res,num[st]); //get left part min
                bs(num, mid+1, ed,res); //serch right part
    int findMin(vector<int> &num) {
        int n = num.size();
        int res = num[0];
        return res;


class Solution:
    # @param num, a list of integer
    # @return an integer
    def bs(self, num, st, ed, res):
        if st > ed:
            return res
            mid = st + (ed - st)/2
            while num[mid]==num[ed] and mid!=ed:
                ed -= 1
            while num[mid]==num[st] and mid!=st:
                st += 1
            if num[mid] < num[ed] or mid == ed:
                res = min(res, num[mid])
                return self.bs(num, st, mid-1, res)
                res = min(res, num[st])
                return self.bs(num, mid+1, ed, res)
    def findMin(self, num):
        n = len(num)
        res = num[0]
        return self.bs(num, 0, n-1, res)

1 comment: