153. 寻找旋转排序数组中的最小值

📝 题目描述

已知一个长度为 n 的数组，预先按升序排列，经 1 到 n 次旋转后得到输入数组（旋转1次指将数组最后一个元素移到开头）。数组元素互不相同，要求设计时间复杂度为 O(log n) 的算法，找出该数组的最小值。

---

📌 示例

示例 1

输入：

nums = [3,4,5,1,2]

输出：

1

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

示例 2

输入：

nums = [4,5,6,7,0,1,2]

输出：

0

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

示例 3

输入：

nums = [11,13,15,17]

输出：

11

解释：原数组旋转4次后与原数组一致，最小值为11。

---

🚀 最优解：二分查找（比较中点与右端点）

🔍 思路解析

核心策略：旋转数组的“最小值”是数组的“分界点”（左侧升序、右侧升序且左侧所有元素 > 右侧所有元素），通过二分比较中点与右端点，缩小最小值所在范围。

1. 初始化双指针 left=0、right=nums.length-1；
2. 当 left < right 时，计算中点 mid = (left + right) / 2；
3. 比较 nums[mid] 与 nums[right]：
   • 若 nums[mid] < nums[right]：最小值在左半部分（含 mid），令 right = mid；
   • 若 nums[mid] > nums[right]：最小值在右半部分（不含 mid），令 left = mid + 1；
4. 当 left == right 时，nums[left] 即为最小值。

---

✅ 完整代码（Java）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        // 创建解决方案对象并计算结果
        Solution solution = new Solution();
        int result = solution.findMin(nums);

        // 输出结果
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        // 二分缩小范围，直到left == right
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < nums[right]) {
                // 最小值在左半部分（含mid）
                right = mid;
            } else {
                // 最小值在右半部分（不含mid）
                left = mid + 1;
            }
        }
        // 此时left == right，对应的值即为最小值
        return nums[right];
    }
}

---

🧠 通俗易懂解释

可以把旋转数组想象成“两段上坡路，中间有个下坡的最低点”：

• 比如数组 [3,4,5,1,2]，前半段 [3,4,5] 是上坡，后半段 [1,2] 也是上坡，但前半段的终点（5）比后半段的起点（1）高；
• 用二分法找这个“最低点”：每次看中点 mid，如果中点比右端点小，说明“最低点”在中点左边；如果中点比右端点大，说明“最低点”在中点右边；
• 不断缩小范围，最后剩下的那个点就是“最低点”（最小值）。

以示例1 nums = [3,4,5,1,2] 为例：

1. left=0, right=4，mid=2，nums[2]=5 > nums[4]=2 → 最小值在右半部分，left=3；
2. left=3, right=4，mid=3，nums[3]=1 < nums[4]=2 → 最小值在左半部分，right=3；
3. left=3 == right=3，返回 nums[3]=1。

---

⏱ 时间复杂度

O(log n)

每次二分将范围缩小一半，遍历次数为数组长度的对数级别。

---

💾 空间复杂度

O(1)

仅使用3个指针变量，无额外空间消耗。

二分 nums[mid] < nums[nums.length - 1] r. = mid mid可以判断在左半部分还是右半部分 例：45 123