leetcode (力扣) 154. 寻找旋转排序数组中的最小值 I+II (二分法)

本文主要是介绍leetcode (力扣) 154. 寻找旋转排序数组中的最小值 I+II (二分法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

题目描述
思路分析
完整代码

题目描述

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

示例 2：
输入：nums = [2,2,2,0,1]
输出：0

思路分析

寻找旋转排序数组中的最小值有俩题，一个中等一个困难，区别就在于数组中是否有重复数字。

先说一下中等的这个题。

题目要求：
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
无疑直接二分法。

例子：nums = [4,5,6,7,0,1,2,3]

直接设置头尾指针，left=0 。right = len(nums)-1。
开始二分。

这里的关键点就在于如何划分后续的left和right。

直接看一遍步骤：

mid = (left+right)//2 = 3
此时mid指向数组中的7，显然最小值还在右边，所以当nums[mid]>nums[right]时，left = mid+1
同理，小于的时候 right = mid，这里要找的是最小值，所以当大于的时候可以直接+1跳过mid，小于的时候由于并无法确定mid是否为最小值，所以不能+1跳过。

然后二分就结束了。这题就是这么简单。

再说一下这个困难题

困难题目在中等的基础上加了一个条件，就是数组中可能存在相同的元素。

假设有例子 nums=[4.5.6.7.0.1.1]

开始时mid指向7，right指向1.显然数组向右边收缩。
left = 4，mid=5，right=6.此时 nums[mid] == nums[right]，所以right = right-1.去掉重复值，然后继续循环。

细节：
为什么本题二分法不用 nums[m] 和 nums[i] 作比较？

二分目的是判断 m 在哪个排序数组中，从而缩小区间。而在 nums[m]>nums[i]，情况下，无法判断 m 在哪个排序数组中。本质上是由于 j 初始值肯定在右排序数组中； i 初始值无法确定在哪个排序数组中。举例如下：

对于以下两示例，当 i=0,j=4,m=2 时，有 nums[m] > nums[i] ，而结果不同。

[1,2,3,4,5]旋转点 x=0 ： m 在右排序数组（此示例只有右排序数组）。
[3,4,5,1,2]旋转点 x=3 ： m 在左排序数组。

完整代码

153题。
class Solution:def findMin(self, nums: List[int]) -> int:left = 0right = len(nums)-1while left<right:mid =  (left+right)//2if nums[mid] > nums[right]:left = mid+1else:right = midreturn nums[left]154题。
class Solution:def findMin(self, nums: List[int]) -> int:left = 0right = len(nums)-1while left<right:mid = (left+right)//2if nums[mid]>nums[right]:left = mid+1elif nums[mid]<nums[right]:right = midelse:right-=1return nums[left]