剑指Offer 11. 旋转数组的最小数字

leetcode 数组简单二分查找

剑指Offer

发布日期: 2020-10-27

更新日期: 2020-10-27

文章字数: 397

阅读时长: 1 分

阅读次数:

一、题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组[3,4,5,1,2]为[1,2,3,4,5]的一个旋转，该数组的最小值为1。

示例 1：

输入：[3,4,5,1,2]
输出：1

示例2：

输入：[2,2,2,0,1]
输出：0

注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

二、思路

1. 遍历

直接对数组进行遍历。因为该数组为递增排序，然后旋转之后的。所以最小值一定小于前边那个数，也就是最小值与最大值的分界处。

2. 二分查找

题解

三、代码

1. 遍历

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        n = len(numbers)
        for i in range(n-1):
            if numbers[i] > numbers[i+1]:
                return numbers[i+1]
        # n == 0 or 数组里边元素都是相等
        return numbers[0]

2. 二分查找

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        left, right = 0, len(numbers)-1
        while left < right:
            cur = left + (right - left) // 2
            if numbers[cur] > numbers[right]:
                left = cur + 1
            elif numbers[cur] < numbers[right]:
                right = cur
            else:
                right -= 1
        return numbers[left]