• 题目难度：简单

• 题目描述：

  有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。
• 数据范围：1≤ n ≤10000，数组中任意元素的值: 0≤ val ≤10000
• 要求：空间复杂度：O(1) ，时间复杂度： O(logn)

• 实例1：

  输入：[3,4,5,1,2]
  返回值：1

• 思路1：暴力枚举

  时间复杂度：O(n)

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

• 思路2：二分法

  时间复杂度：O(logn)
  
  

class Solution {
public:
   int minNumberInRotateArray(vector<int> rotateArray) {
        int l = 0, r = rotateArray.size() - 1;
        while (l < r) {
            int mid = (l + r) >> 1
            if (rotateArray[mid] > rotateArray[r]) l = mid + 1;
            else if (rotateArray[mid] < rotateArray[r]) r = mid;
            else r--; 
        }
        return rotateArray[l];
    } 
}

😘😘😘😘😘😘😘😘😘😘😘😘😘