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

• 标签：数组、二分查找
• 难度：中等

题目大意 #

给定一个数组 nums，nums 是有升序数组经过「旋转」得到的。但是旋转次数未知。数组中不存在重复元素。

要求：找出数组中的最小元素。

• 旋转：将数组整体右移。

解题思路 #

数组经过「旋转」之后，会有两种情况，第一种就是原先的升序序列，另一种是两段升序的序列。

第一种的最小值在最左边。第二种最小值在第二段升序序列的第一个元素。

1
2
3
4
5
6

          *
        *
      *
    *
  *
*

1
2
3
4
5
6

    *
  *
*
          *
        *
      *

最直接的办法就是遍历一遍，找到最小值。但是还可以有更好的方法。考虑用二分查找来降低算法的时间复杂度。

创建两个指针 left、right，分别指向数组首尾。让后计算出两个指针中间值 mid。将 mid 与两个指针做比较。

1. 如果 nums[mid] > nums[right]，则最小值不可能在 mid 左侧，一定在 mid 右侧，则将 left 移动到 mid + 1 位置，继续查找右侧区间。
2. 如果 nums[mid] ≤ nums[right]，则最小值一定在 mid 左侧，或者 mid 位置，将 right 移动到 mid 位置上，继续查找左侧区间。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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[right]:
                left = mid + 1
            else:
                right = mid
        return nums[left]