06 旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组[3,4,5,1,2]为[1,2,3,4,5]的一个旋转，该数组的最小值为1。

示例：

输入: [3,4,5,1,2]
输出: 1

输入: [2,2,2,0,1]
输出: 0

解题思路

核心思想：利用二分查找，根据旋转数组的特性缩小搜索范围。

关键步骤：

1. 左指针指向数组开头，右指针指向数组末尾
2. 计算中间位置 mid = (left + right) // 2
3. 如果 nums[mid] > nums[right]，说明最小值在右半部分，left = mid + 1
4. 如果 nums[mid] < nums[right]，说明最小值在左半部分（包括mid），right = mid
5. 如果 nums[mid] == nums[right]，无法判断，只能逐个缩小，right -= 1
6. 当 left == right 时，找到最小值

时间复杂度：平均O(log n)，最坏O(n)（当所有元素相等时） 空间复杂度：O(1)

Python 实现

def min_number_in_rotate_array(nums):
    """
    寻找旋转数组的最小数字

    Args:
        nums: 旋转数组

    Returns:
        int: 最小数字
    """
    if not nums:
        return -1

    left, right = 0, len(nums) - 1

    # 如果数组没有旋转
    if nums[left] < nums[right]:
        return nums[left]

    while left < right:
        mid = (left + right) // 2

        if nums[mid] > nums[right]:
            # 最小值在右半部分
            left = mid + 1
        elif nums[mid] < nums[ right]:
            # 最小值在左半部分
            right = mid
        else:
            # 无法判断，逐个缩小
            right -= 1

    return nums[left]


# 测试代码
if __name__ == "__main__":
    test_cases = [
        [3, 4, 5, 1, 2],
        [2, 2, 2, 0, 1],
        [1, 2, 3, 4, 5],
        [2, 1],
        [1, 1, 1, 1],
    ]

    for case in test_cases:
        print(f"{case} → {min_number_in_rotate_array(case)}")

# 输出:
# [3, 4, 5, 1, 2] → 1
# [2, 2, 2, 0, 1] → 0
# [1, 2, 3, 4, 5] → 1
# [2, 1] → 1
# [1, 1, 1, 1] → 1

图解

示例: [3, 4, 5, 1, 2]

初始: left=0, right=4
      nums[left]=3, nums[right]=2
      nums[mid]=nums[2]=5 > nums[right]=2
      → 最小值在右半部分，left=3

第二轮: left=3, right=4
       nums[mid]=nums[3]=1 < nums[right]=2
       → 最小值在左半部分，right=3

第三轮: left=3, right=3
       left == right，找到最小值
       返回 nums[3]=1