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.


Analysis:
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.

Code(C++):

class Solution {
public:
    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];
        bs(num,0,n-1,res);
        return res;
    }
};

Code(Python):

class Solution:
    # @param num, a list of integer
    # @return an integer
    def bs(self, num, st, ed, res):
        if st > ed:
            return res
        else:
            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)
            else:
                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)