解题思路： ​

为精简篇幅，本文将数组 $numbers$ 缩写为 $nums$ 。

如下图所示，寻找旋转数组的最小元素即为寻找 右排序数组 的首个元素 $nums[x]$ ，称 $x$ 为 旋转点 。

排序数组的查找问题首先考虑使用 二分法 解决，其可将 遍历法 的 线性级别 时间复杂度降低至 对数级别 。

算法流程： ​

1. 初始化： 声明 $i$, $j$ 双指针分别指向 $nums$ 数组左右两端；
2. 循环二分： 设 $m = (i + j) / 2$ 为每次二分的中点（ "/" 代表向下取整除法，因此恒有 $i \leq m < j$ ），可分为以下三种情况：
   1. 当 $nums[m] > nums[j]$ 时： $m$ 一定在 左排序数组 中，即旋转点 $x$ 一定在 $[m + 1, j]$ 闭区间内，因此执行 $i = m + 1$；
   2. 当 $nums[m] < nums[j]$ 时： $m$ 一定在 右排序数组 中，即旋转点 $x$ 一定在$[i, m]$ 闭区间内，因此执行 $j = m$；
   3. 当 $nums[m] = nums[j]$ 时： 无法判断 $m$ 在哪个排序数组中，即无法判断旋转点 $x$ 在 $[i, m]$ 还是 $[m + 1, j]$ 区间中。解决方案： 执行 $j = j - 1$ 缩小判断范围，分析见下文。
3. 返回值： 当 $i = j$ 时跳出二分循环，并返回 旋转点的值 $nums[i]$ 即可。

正确性证明： ​

当 $nums[m] = nums[j]$ 时，无法判定 $m$ 在左（右）排序数组，自然也无法通过二分法安全地缩小区间，因为其会导致旋转点 $x$ 不在区间 $[i, j]$ 内。举例如下：

设以下两个旋转点值为 $0$ 的示例数组，则当 $i = 0$, $j = 4$ 时 $m = 2$ ，两示例结果不同。 示例一 $[1, 0, 1, 1, 1]$ ：旋转点 $x = 1$ ，因此 $m = 2$ 在 右排序数组 中。 示例二 $[1, 1, 1, 0, 1]$ ：旋转点 $x = 3$ ，因此 $m = 2$ 在 左排序数组 中。

而证明 $j = j - 1$ 正确（缩小区间安全性），需分为两种情况：

1. 当 $x < j$ 时： 易得执行 $j = j - 1$ 后，旋转点 $x$ 仍在区间 $[i, j]$ 内。

2. 当 $x = j$ 时： 执行 $j = j - 1$ 后越过（丢失）了旋转点 $x$ ，但最终返回的元素值 $nums[i]$ 仍等于旋转点值 $nums[x]$ 。

   1. 由于 $x = j$ ，因此 $nums[x] = nums[j] = nums[m] \leq number[i]$ ;
   2. 又由于 $i \leq m <j$ 恒成立，因此有 $m < x$ ，即此时 $m$ 一定在左排序数组中，因此 $nums[m] \geq nums[i]$ ;

• 综合 1. , 2. ，可推出 $nums[i] = nums[m]$ ，且区间 $[i, m]$ 内所有元素值相等，即有：

$$ nums[i] = nums[i+1] = \cdots = nums[m] = nums[x] $$

• 此时，执行 $j = j - 1$ 后虽然丢失了旋转点 $x$ ，但之后区间 $[i, j]$ 只包含左排序数组，二分下去返回的一定是本轮的 $nums[i]$ ，而其与 $nums[x]$ 相等。

综上所述，此方法可以保证返回值 $nums[i]$ 等于旋转点值 $nums[x]$ ，但在少数特例下 $i \ne x$ ；而本题目只要求返回 “旋转点的值” ，因此本方法正确。

补充思考： 为什么本题二分法不用 $nums[m]$ 和 $nums[i]$ 作比较？

二分目的是判断 $m$ 在哪个排序数组中，从而缩小区间。而在 $nums[m] > nums[i]$情况下，无法判断 $m$ 在哪个排序数组中。本质上是由于 $j$ 初始值肯定在右排序数组中； $i$ 初始值无法确定在哪个排序数组中。举例如下：

对于以下两示例，当 $i = 0, j = 4, m = 2$ 时，有 nums[m] > nums[i] ，而结果不同。 $[1, 2, 3, 4 ,5]$ 旋转点 $x = 0$ ： $m$ 在右排序数组（此示例只有右排序数组）； $[3, 4, 5, 1 ,2]$ 旋转点 $x = 3$ ： $m$ 在左排序数组。

<,,,,,,,,>

复杂度分析： ​

• 时间复杂度 $O(\log_2 N)$ ： 在特例情况下（例如 $[1, 1, 1, 1]$），会退化到 $O(N)$。
• 空间复杂度 $O(1)$ ： $i$ , $j$ , $m$ 变量使用常数大小的额外空间。

代码： ​

class Solution:
    def minArray(self, numbers: [int]) -> int:
        i, j = 0, len(numbers) - 1
        while i < j:
            m = (i + j) // 2
            if numbers[m] > numbers[j]: i = m + 1
            elif numbers[m] < numbers[j]: j = m
            else: j -= 1
        return numbers[i]

class Solution {
    public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[i];
    }
}

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int i = 0, j = numbers.size() - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[i];
    }
};

实际上，当出现 $nums[m] = nums[j]$ 时，一定有区间 $[i, m]$ 内所有元素相等 或 区间 $[m, j]$ 内所有元素相等（或两者皆满足）。对于寻找此类数组的最小值问题，可直接放弃二分查找，而使用线性查找替代。

class Solution:
    def minArray(self, numbers: [int]) -> int:
        i, j = 0, len(numbers) - 1
        while i < j:
            m = (i + j) // 2
            if numbers[m] > numbers[j]: i = m + 1
            elif numbers[m] < numbers[j]: j = m
            else: return min(numbers[i:j])
        return numbers[i]

class Solution {
    public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else {
                int x = i;
                for(int k = i + 1; k < j; k++) {
                    if(numbers[k] < numbers[x]) x = k;
                }
                return numbers[x];
            }
        }
        return numbers[i];
    }
}

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int i = 0, j = numbers.size() - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else {
                int x = i;
                for(int k = i + 1; k < j; k++) {
                    if(numbers[k] < numbers[x]) x = k;
                }
                return numbers[x];
            }
        }
        return numbers[i];
    }
};