leetcode 旋转数组的最小数字【二分】

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

( 例如，数组 [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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路： 首先这个数组在局部上仍是有序的，只是被分为了前后两个有序的部分。

我们可以知道，当一个有序数组被旋转之后，前半部分和后半部分分别有序，并且前半部分的值必定大于后半部分，并且题目所求最小数字位于前半部分与后半部分的交界处。

如何定位最小数字的位置，我们使用二分时，会选出一个Mid值进行一定条件的比较，以判断向某个方向缩小搜索范围。

此时我们有一个位于中间的数字mid,可以将其与最左边的数进行比较，当发现大于最左边的数时，说明当前mid的值位于有序数组的前半部分，这是显而易见的，因为若该mid位置的值小于最左边的值，那么明显是后半部分的值，因为前半部分的所有值都大于等于后半部分的值。由此定位到我们正搜索的位置，并且我们知道，最小值位于右半部分的第一个值，，位于左半部分的最后一个值之后。

通过比较左右边界的大小的信息，我们容易得出目标值位于左边还是右边，当Mid大于左边界的值时，向右搜索，尽量使搜索范围靠近右半部分。

当mid的值小于左边界时，该值一定位于右半部分，此时可能当前值以及当前值的左边存在目标值。于是向左搜索。

在二分的过程中，我们可以多次判断当前值与前后两值的关系，当前一个值大于当前值，或后一个值小于当前值时【不满足单调递增的性质】说明已经找到了两部分的边界，可以直接返回结果

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if nums[0]<=nums[-1]:
            return nums[0]
        l=0
        r=len(nums)-1
        while l<=r:
            mid=(l+r)//2
            if nums[mid]>nums[mid+1]:
                return nums[mid+1]
            if nums[mid]<nums[mid-1]:
                return nums[mid]
            if nums[mid]>nums[l] :
                l=mid+1
            else:r=mid-1

最后

以上就是无聊秀发为你收集整理的leetcode 旋转数组的最小数字【二分】的全部内容，希望文章能够帮你解决leetcode 旋转数组的最小数字【二分】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。