剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

方法1：暴力查找最小值（时间复杂度O(n)，空间复杂度O(n)）

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int min=0;
		if(rotateArray.empty())
			return 0;
		min=rotateArray[0];	
		for(int i=1;i<rotateArray.size();i++)
		{
		 	if(min>rotateArray[i])
		 		min=rotateArray[i];
		}
		return min;
    }
};

方法2：二分查找（时间复杂度O(logn)，空间复杂度O(1)）

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int low=0;
        int high=rotateArray.size()-1;
        int mid=(low+high)/2;
        //先判断是否已经有序 
        if(rotateArray[low]<rotateArray[high])
            return rotateArray[low]; 
        while(low<high)
        {

            if(rotateArray[low]<rotateArray[high])
            {
                return rotateArray[low]; //已经有序	
            }	
            else if(rotateArray[mid]>rotateArray[low])
            {
                low=mid+1;	
            } 
            else if(rotateArray[mid]<rotateArray[low])
            {
                high=mid;
                low++;	
            } 
            else
            {
                //可能有相等的时候 
                low++;	
            }
            mid=(low+high)/2;
        } 
        return rotateArray[mid]; 
    }
};