leetcode153. 寻找旋转排序数组中的最小值——二分查找

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

已知一个长度为 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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

题目链接：153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode） (leetcode-cn.com)

二分查找

思路：

• 首先先处理两个特殊情况：

  • 数组的长度为1，则最小值为nums[0]
  • 数组经过n次旋转之后仍为原数组即nums[n-1] > num[0]，依旧返回nums[0]

• 经过旋转的数组会形成前后两个有序数组

• 设置左右两个指针left 和 right

• 中间值 mid = (left+right)//2

• 最小值会在哪里？

  • 若num[mid] < nums[right] 说明nums[mid:right]是一个有序数组，最小值在左边
  • 若nums[mid] > nums[right] 说明最小值在nums[mid:right]中间

• 退出while循环的条件是left == right，于是最后返回 nums[left] 或者 nums[right]

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

原文：https://www.cnblogs.com/waitting975/p/15311875.html