每日一道算法之--寻找旋转排序数组中的最小值

数组二分查找

Word count: 590Reading time: 2 min

 2020/03/11   Share

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

力扣第153题:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/

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

( 例如，数组 [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

这道题是剑指的原题的简单版,这里可以假设假设数组中不存在重复元素。找出其中最小的元素,直接遍历数组找到最小的元素不就好了吗,时间复杂度也为O(n),但是这样就和旋转数组没什么关系了,所以就算做出来了,面试也没什么效果。

二分查找思想

我们知道在一个有序数组中，用二分法查找一个数，时间复杂度为O（logn），效率非常高。那么这道题也是有序数组的变形，应该也能用二分法。

可以看到，旋转数组分为了两部分，左右两部分也都是有序的
而且旋转数组的分界点，正是最小的元素
所以我们可以利用双指针，开始时分别指向数组的最前（左部分）和最后（右部分），然后去中间点，如果中间点的值比最前的点大，那么证明中间点在左部分，且最小元素在右部分，所以可以将左部分的指针指向中间点，这就是实现二分的思想。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if not nums: return -1
        if len(nums) == 1: return nums[0]
        left, right = 0, len(nums) - 1
        mid = left
        # 左边的元素比右边的大
        while nums[left] >= nums[right]:
            # 最小元素作为边界,即为右边区间的第一个元素
            if right - left == 1:
                mid = right
                break
            mid = left + (right - left) //2
            if nums[mid] >= nums[left]:
                left = mid
            else:
                right = mid
        return nums[mid]