已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：

输入： nums = [11,13,15,17]
输出： 11
解释： 原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

题目解析

题意总结： 给定一个原本升序排列但经过若干次旋转的数组（元素互不相同），要求找到数组中的最小元素。 核心约束： 题目明确要求时间复杂度必须为 O(log n)，这直接指明了本题必须使用二分查找算法。

解题思路

旋转后的数组有一个非常显著的特征：它被切分成了两个局部的升序子数组。并且，左边子数组的所有元素一定大于右边子数组的所有元素（除非旋转了 n 次，即没有真正旋转，此时整体是一个升序数组）。

我们要找的最小值，本质上就是这两个局部升序数组的“分界点”。

我们可以使用双指针 left 和 right 来划定搜索区间，每次计算中间位置 mid，将 nums[mid] 与区间最右侧的元素 nums[right] 进行比较，以此来判断最小值到底在左半部分还是右半部分。

具体逻辑如下：

1. 初始化指针：left = 0，right = nums.length - 1。
2. 循环条件：left < right。注意这里不需要 <=，因为当 left == right 时，我们就锁定到唯一的值了，它就是我们要找的最小值。
3. 计算中点：mid = left + (right - left) / 2，防止整型溢出。
4. 核心比较：比较 nums[mid] 和 nums[right] 的大小关系：
   • 情况 A：nums[mid] > nums[right] 说明 mid 位置处于左边的递增子数组中，最小值一定在 mid 的右侧。 操作：left = mid + 1。
   • 情况 B：nums[mid] < nums[right] 说明 mid 位置及右侧是严格递增的，即最小值可能就是 nums[mid] 本身，也可能在 mid 的左侧。 操作：right = mid。（注意：这里不能是 mid - 1，否则可能会把最小值漏掉）。
   • 情况 C：nums[mid] == nums[right] 由于题目明确说明数组元素互不相同，这种情况在此题中不会发生。

复杂度分析：

• 时间复杂度：O(log n)。每次循环搜索空间减半，属于标准的二分查找时间复杂度。
• 空间复杂度：O(1)。只使用了几个常数级别的指针变量，没有占用额外的内存空间。

Java 实现

class Solution {
    public int findMin(int[] nums) {
        // 初始化左右指针
        int left = 0;
        int right = nums.length - 1;

        // 当 left == right 时，循环结束，我们就找到了最小值
        while (left < right) {
            // 计算中间索引，这种写法可以有效避免 left + right 导致的整型溢出
            int mid = left + (right - left) / 2;

            // 将中间元素与右边界元素进行比较
            if (nums[mid] > nums[right]) {
                // 如果中间值大于最右边的值，说明发生了旋转
                // 且最小值一定在 mid 的右边（不包括 mid）
                // 比如：[3, 4, 5, 1, 2]，mid 对应 5，右边界是 2
                left = mid + 1;
            } else {
                // 如果中间值小于最右边的值，说明 mid 到 right 这一段是单调递增的
                // 那么最小值就在 mid 的左边，或者是 mid 本身
                // 比如：[4, 5, 1, 2, 3]，mid 对应 1，右边界是 3
                // 注意这里不能用 right = mid - 1，因为 mid 可能正是我们要找的最小值
                right = mid;
            }
        }

        // 循环结束时，left 和 right 指向同一个位置，该位置即为最小值的索引
        return nums[left];
    }
}