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

题解思路

1. 旋转数组的特点

旋转后的数组由 两个递增的子数组 组成，其中 最小值 是数组的 旋转点，即第二个递增子数组的 起点。

例如：

原数组:     [0, 1, 2, 4, 5, 6, 7]
旋转后:     [4, 5, 6, 7, 0, 1, 2]   （最小值 0）

目标是 在 $O(\log n)$ 时间内找到这个最小值。

2. 二分查找解法

二分查找的关键在于 判断哪一部分是有序的，然后调整搜索范围：

• 如果 nums[mid] > nums[right]，说明最小值一定在 mid 右侧，因为 mid 及其左侧仍是递增的，最小值被旋转到了右侧。
• 如果 nums[mid] < nums[right]，说明最小值一定在 mid 左侧或就是 mid，因为 mid 及其右侧是递增的，意味着 mid 可能是最小值。

复杂度分析

• 时间复杂度：$O(\log n)$，因为使用了二分查找，每次都缩小一半范围。
• 空间复杂度：$O(1)$，仅使用常数级别的额外空间。

代码实现

Python 代码

import sys

def find_min(nums):
    left, right = 0, len(nums) - 1

    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:  # 说明最小值在右侧
            left = mid + 1
        else:  # 说明最小值在左侧或就是 mid
            right = mid

    return nums[left]

# 读取输入
n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().split()))

# 输出结果
print(find_min(nums))

Java 代码

import java.util.Scanner;

public class Main {
    public static int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }

    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();
        }
        System.out.println(findMin(nums));
    }
}

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

int findMin(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return nums[left];
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    cout << findMin(nums) << endl;
    return 0;
}

题目内容

已知一个长度为 $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)$的算法解决此问题。

输入描述

• 第一行输入一个整数 n，表示数组的长度。
• 第二行输入 n 个整数，表示旋转后的数组 nums。 输出描述

输出描述

输出数组中的最小元素。

样例1

输入

5
3 4 5 1 2

输出

1

说明

原数组为$[1,2,3,4,5]$ ，旋转 $3$次得到输入数组。

样例2

输入

7
4 5 6 7 0 1 2

输出

0

说明

原数组为$[0,1,2,4,5,6,7]$ ，旋转 $4$ 次得到输入数组

样例3

输入

4
11 13 15 17

输出

11

说明

原数组为 $[11,13,15,17]$ ，旋转$4$次得到输入数组

提示：

• $n == nums.length$
• $1 <= n <= 5000$
• $-5000 <= nums[i] <= 5000$
• $nums$中的所有整数互不相同
• $nums$ 原来是一个升序排序的数组，并进行了 $1$ 至 $n$ 次旋转