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

题目链接：153. 寻找旋转排序数组中的最小值

题目描述

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组 nums 。

例如，原数组 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)$ 的算法解决此问题。

核心思考：二分查找（基于末尾值的枢轴比较）

对于一个旋转过的排序数组，它实际上是由两个有序子数组拼接而成的。最小值就是那个特殊的“转折点”或称“断层点”。由于要满足 $O(\log n)$，我们必须使用二分查找。

1. 寻找判定基准：
   在旋转数组中，我们通常将 nums[mid] 与数组的最右侧元素 nums[-1]（或者说是区间末位）进行比较。
2. 决策逻辑：
   • 如果 nums[mid] > nums[-1]：说明 mid 当前位于数组前半段那个较大的升序序列中。根据旋转特性，最小值必然在 mid 的右侧。因此 left = mid + 1。
   • 如果 nums[mid] < nums[-1]：说明 mid 当前已经进入了数组后半段那个较小的升序序列，或者数组根本就没有旋转。最小值可能就是 mid 自己，或者在 mid 的左侧。因此 right = mid - 1。
3. 收敛结果：循环结束后，left 指针所在的位置即为找到的最小值索引。

这种“蓝红划分”式的二分思想能够精准定位到数组单调性发生突变的那个点。

解题思路 (Python)

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        # 二分查找，针对旋转断层进行定位
        while left <= right:
            mid = left + (right - left) // 2
            # 这里的判定核心是与数组最后一个数进行对比
            if nums[mid] > nums[-1]:
                # 中间值大，说明还处于旋转前半段的高位区，最小值在右边
                left = mid + 1
            else:
                # 中间值小，说明已经进入低位区或整体升序，最小值可能是 mid 本身或在其左边
                right = mid - 1

        # left 最终指向找到的最小值
        return nums[left]

复杂度分析

• 时间复杂度：$O(\log N)$，其中 $N$ 是数组的长度。标准二分查找过程。
• 空间复杂度：$O(1)$，仅使用了常数个指针变量。
  说明：为了逻辑更符合常用的闭区间写法，代码对 right 的初始值和 while 后续逻辑进行了标准二分对齐校对。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

num1 num2 num3 ... numN

输入一行整数数组，以空格分隔。

完整代码：

import sys

class Solution:
    def findMin(self, nums: List[int]) -> int:
    left = 0
            right = len(nums) - 1
            # 二分查找，针对旋转断层进行定位
            while left <= right:
                mid = left + (right - left) // 2
                # 这里的判定核心是与数组最后一个数进行对比
                if nums[mid] > nums[-1]:
                    # 中间值大，说明还处于旋转前半段的高位区，最小值在右边
                    left = mid + 1
                else:
                    # 中间值小，说明已经进入低位区或整体升序，最小值可能是 mid 本身或在其左边
                    right = mid - 1

            # left 最终指向找到的最小值
            return nums[left]

def main():
    nums = list(map(int, sys.stdin.read().strip().split()))

    sol = Solution()
    result = sol.findMin(nums)
    print(result)

if __name__ == "__main__":
    main()

运行示例：

echo "2 -1 3 4 -5" | python solution.py