算法入门02旋转数组的最小数字

解法一：直接遍历，找最小值

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        //第一种方法 (O(n))
        int minNum=INT_MAX;
        for(int i=0;i<rotateArray.size();i++){
            minNum=min(minNum,rotateArray[i]);
        }
        return minNum;
    }
};  

1
2
3
4
5
6
7
8
9
10
11
12

解法一面试官肯定不是想让我们这样求解

解法二:因为这是一个非递减的数组，所以旋转之后呢，只要我们从开头遍历，肯定会遇到一个比前一个小的，也就是遇到最小的那个，就可以直接输出了

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        //解法二
        if(rotateArray.size()==0) return 0;
        for(int i=1;i<rotateArray.size();i++){
            if(rotateArray[i]<rotateArray[i-1])
                return rotateArray[i];
        }
        return rotateArray[0];
    }
};  

1
2
3
4
5
6
7
8
9
10
11
12
13

解法二：或者是我们直接上来使用库函数对数据进行排序

//解法二:
        sort(rotateArray.begin(),rotateArray.end());
        return rotateArray[0];
1
2
3

解法三:当数据很多的时候，那么前两个方法就不太可行了，这时候我们应该想到二分查找，划分区间来解决.
由题意我们模拟情况:

  int left=0;
        int right=rotateArray.size()-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(rotateArray[left]<rotateArray[right])
                return rotateArray[left];
            else if(rotateArray[right]<rotateArray[mid]){
                left=mid+1;
            }   
            else if(rotateArray[right]>rotateArray[mid]){
                right=mid;
            }
            else 
                right--;
        }
        return rotateArray[left];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

如有错误，多多指教！