旋轉數組中的最小數字 - acm1314－IT工程師數位筆記本

文章出處

思路：二分查找的變形，注意開頭和結尾是相同數字時的特殊情況。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size() == 0)
            return 0;
        int left = 0, right = rotateArray.size()-1;
        int mid = left; 
        // 確保旋轉
        while(rotateArray[left] >= rotateArray[right])
        {
            if(right - left == 1)
            {
                mid = right; 
                break; 
            }
            mid = left + (right - left) / 2; 
            // 特殊情況， 進行順序查找
            if(rotateArray[left] == rotateArray[right] && rotateArray[mid] == rotateArray[left])
                return orderSeach(rotateArray, left, right);
            
            if(rotateArray[mid] >= rotateArray[left])
                left = mid; 
            if(rotateArray[mid] <= rotateArray[right])
                right = mid; 
        }
        return rotateArray[mid]; 
    }

private:
    int orderSeach(vector<int>& arr,int left,int right)
    {
        int min = arr[left]; 
        for(int i = left+1; i <= right ; i++)
            if(min > arr[i])
                min = arr[i]; 
        
        return min; 
    }
};