Catalogue：array - 分治法

Question

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.

First try

class Solution {
public:
    int findMin(vector<int> &num) {
        ret = 0;
        binarySearch(num,0,num.size()-1);
        return num[ret];
    }
    
    void binarySearch(vector<int> &num, int start, int end)
    {
        if(end-start<=1)
        {
            if(num[end]>num[start]) return;
            else
            {
                ret = end;
                return;
            }
        }
        
        int mid = (start + end) >> 1;
        if(num[start]>num[mid])
          binarySearch(num, start, mid);
        else if(num[mid+1]>num[end])
          binarySearch(num, mid+1, end);
        else if(num[mid]>num[mid+1])
          ret = mid+1;
    }
private:
    int ret;
};

Second try

有重复元素，用while循环忽略

class Solution {
public:
    int findMin(vector<int> &num) {
        ret = 0;
        binarySearch(num,0,num.size()-1);
        return num[ret];
    }
    
    void binarySearch(vector<int> &num, int start, int end)
    {
        if(end-start<=1)
        {
            if(num[end]>num[start]) return;
            else
            {
                ret = end;
                return;
            }
        }
        
        int mid = (start + end) >> 1;
        while(start!=mid && num[start] == num[mid])
        {
            mid--;
        }
        while(end!=mid && num[end] == num[mid])
        {
            mid++;
        }
        if(num[start] > num[mid])
          binarySearch(num, start, mid);
        else if(num[mid+1] >= num[end])
          binarySearch(num, mid+1, end);
        else if(num[mid]>num[mid+1])
          ret = mid+1;
    }
private:
    int ret;
};

Last executed input:[3,1,1]

Third try

时刻注意数据越界的检查

class Solution {
public:
    int findMin(vector<int> &num) {
        ret = 0;
        binarySearch(num,0,num.size()-1);
        return num[ret];
    }
    
    void binarySearch(vector<int> &num, int start, int end)
    {
        if(end-start<=1)
        {
            if(num[end]>num[start]) return;
            else
            {
                ret = end;
                return;
            }
        }
        
        int mid = (start + end) >> 1;
        int mid2 = mid;
        while(start!=mid2 && num[start] == num[mid2])
        {
            mid2--;
        }
        if(num[start] > num[mid2])
          binarySearch(num, start, mid2);
        else
        {
            mid2 = mid;
            while(end!=mid && num[end] == num[mid])
            {
                mid++;
            }
            if(num[mid] > num[end])
                binarySearch(num, mid, end);
        }
    }
private:
    int ret;
};

Input: [3,3,1,3]
Output: 3
Expected: 1

Fourth try:

因为有重复，所以可能存在mid和start或end相同，但在start（或end）和mid之前已经经历了递增到递减。

class Solution {
public:
    int findMin(vector<int> &num) {
        ret = 0;
        binarySearch(num,0,num.size()-1);
        return num[ret];
    }
    
    void binarySearch(vector<int> &num, int start, int end)
    {
        if(end-start<=1)
        {
            if(num[end]>num[start]) return;
            else
            {
                ret = end;
                return;
            }
        }
        
        int mid1 = (start + end) >> 1;
        int mid2 = mid1;
        while(start!=mid1 && num[mid1] == num[mid1-1])
        {
            mid1--;
        }
        while(start!=mid1 && num[start] == num[start+1])
        {
            start++;
        }
        if(num[start] > num[mid1] || (start!=mid1 && num[start] > num[mid1-1]))
          binarySearch(num, start, mid1);
        else
        {
            while(end!=mid2 && num[mid2] == num[mid2+1])
            {
                mid2++;
            }
            while(end!=mid2 && num[end] == num[end-1])
            {
                end--;
            }
            if(num[mid2] > num[end] || (end!=mid2 && num[mid2] > num[end-1]))
                binarySearch(num, mid2, end);
        }
    }
private:
    int ret;
};

Find Minimum in Rotated Sorted Array II