题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在重复元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的旋转，该数组的最小值为 1。To do it!
示例1 输入： numbers = [3,4,5,1,2]，输出： 1
示例2 输入： numbers = [2,2,2,0,1]，输出： 0
提示：
n == numbers.length
1 <= n <= 5000
-5000 <= numbers[i] <= 5000
numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

题解

升序数组经过旋转后由两部分升序数组组成，中间会有一个转折点，即为最小值。

遍历查找

直接遍历数组寻找一个升序的转折点。

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int n = numbers.size();
        for (int i = 1; i < n; i++) {
            if (numbers[i] < numbers[i - 1]) {
                return numbers[i];  // 在转折点直接返回
            }
        }
        return numbers[0];  // 没有转折点则返回数组第一个元素（没有旋转
    }
};

时间复杂度：O(n)，空间复杂度：O(1)

二分查找

每次和区间的右端值进行比较，始终保证要寻找的数组最小值在 [low, high] 的区间内。
当 numbers[pivot] == numbers[high] 时，一定有区间 [pivot, high] 或 [low, pivot] 内所有元素相等（可能同时满足），此时可以放弃二分查找，换成线性遍历。

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int lo = 0, hi = numbers.size() - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (numbers[mid] < numbers[hi]) hi = mid;           // numbers[mid] 在 min 右（或 = min
            else if (numbers[mid] > numbers[hi]) lo = mid + 1;  // numbers[mid] 在 min 左（ != 
            else --hi;  // numbers[mid] == numbers[hi] 时不确定 numbers[mid] 在 min 的左或右，但能排除 hi
        }
        return numbers[lo];
    }
};