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

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

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

输出: 1

示例 2:

输入: [4,5,6,7,0,1,2]

输出: 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

思路及算法

方法一：与right比较

一个有序数组，通过旋转后，可视化如下：

通过上图，可以知道以下信息：

• 左边有序数组元素均大于右边有序数组元素
• 最大值的右边就是最小值

二分查找的标准起手

left = 0
right = len(nums) - 1

可求得mid值

比较分析

1. nums[mid] > nums[right]

只有「左边有序数组的元素」才会大于「右边有序数组的最大元素」

所以这说明，mid太靠左了，应该向右收缩

left = mid +1

2. nums[mid] < nums[right]

这也很明显，只有在「右边有序数组的元素」才可能小于 nums[right]

所以说明，mid值太靠右了，应该向左收缩

right = mid

注意：

为什么right 不是 mid + 1，仔细想想当前mid在「右边有序数组」，所以有可能mid就是正确答案，如果改成mid+1则可能找不到

循环退出的条件：

这里所做的 left = mid + 1， right = mid

典型的「左闭右开区间」，看大佬们总结的模板，这种情况就是循环不变式 while left < right

即 当 left = right 时退出循环

动图演示

完整代码

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
        return nums[left]

方法二：与nums[0]比较

通过观察，可以知道，最大值的右侧即最小值

比较分析

让mid值一直与nums[0]比较

1. nums[mid] > nums[0]

表示当前mid所处位置为「左边的有序数组」中

向右收缩

left = mid + 1

2. nums[mid] < nums[0]

毫无疑问，此时mid在「右边的有序数组」中

向左收缩

right = mid - 1

这里可能有疑问了，如果mid刚好就是答案，那么right = mid - 1不就直接错过了吗？

left与right的最小增量都是1

对于right，只会出现两种情况

情况一，执行right = mid - 1之后，依然在「右边的有序数组」中

情况二，mid当前刚好就在「最小值」的位置，则right将会在「最大值」位置，而此后的所有mid值都只会在「左边的有序数组」中，即right的值将不会变换。随着left值的增加，将会在某一时刻满足nums[mid] > nums[mid+1]，即此时 num[mid+1]就是最小值

满足条件

随着left的右移，如果满足以下条件即找到「最小值」

1. nums[mid-1] > nums[mid]

最小值为nums[mid]

2. nums[mid+1] < nums[mid]

最小值为nums[mid+1]

动图演示

完整代码

class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        left, right = 0, n - 1
        # 如果最后一位大于第一位，则表示此数组单调自增，即最小值为第一位元素
        if nums[n-1] > nums[0]:
            return nums[0]

        while left <= right:
            mid = (left + right) >> 1

            if nums[mid] > nums[mid+1]:
                return nums[mid+1]
            if nums[mid] < nums[mid-1]:
                return nums[mid]
            
            if nums[mid] > nums[0]:
                left = mid + 1
            elif nums[mid] < nums[0]:
                right = mid - 1

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

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例 1：

输入: [1,3,5]

输出: 1

示例 2：

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

输出: 0

说明：

这道题是 「寻找旋转排序数组中的最小值」 的延伸题目。
允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

思路及算法

此题相比 153 多了一条设定「数组中可能存在重复的元素」

方法一：与right比较

此时按照上一题的解法，会出现什么问题呢？

举个例子 旋转数组 [3,3,3,1,2,3]

取出mid为3，在上一题中，可以通过mid来区分目标值在哪一侧，而这里则不行了

mid无法明确地将数组一分为二，究其原因是mid和right大小相同造成的，只要解决这一问题，再结合上一题的解法，这道题就可以解决了。

当nums[mid] = nums[right]时，可以保险的将 right -1

right位置的元素，是「右边有序数组中的最大值」，将最大值「减1」，即向左以最小单位「1」进行收缩了一次

在上题的操作中，向左收缩是通过right = mid，进行大范围的快速收缩，这里采用「减1」的方法收缩是最为保险的。

动图演示

完整代码

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
			elif nums[mid] == nums[right]:
                right -= 1
        return nums[left]

参考题解：