旋转数组的最小数字

旋转数组的最小数字_牛客题霸_牛客网

问题简述

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

思路：二分

• 查找区间 [l, r]，初始化 l=0, r=len(arr)-1；

• 则中点 m = (l+r) // 2，有 l <= m < r；

• 因此每次比较 arr[m] 和 arr[r]；

  • 如果 arr[m] < arr[r]，说明答案不在 [m+1,r] ，置 r = m；

  • 如果 arr[m] > arr[r]，说明答案不在 [l,m]，置 l = m + 1；

  • 如果 arr[m] == arr[r]，只能说明答案一定在 [l,r-1]，置 r -= 1；（因为 m != r，所以可以这样写）

    如果每次比较的是 arr[m] 和 arr[l]，碰到 arr[m] == arr[l]，就不能这样写，因为有可能 m == l；

Python

class Solution:
    def minNumberInRotateArray(self , arr: List[int]) -> int:
        # if arr[0] < arr[-1]: return arr[0]
        
        l, r = 0, len(arr) - 1
        
        while l < r:
            m = (l + r) // 2
            
            if arr[m] < arr[r]:  # 说明答案不在 `[m+1,r]` ，置 `r = m`
                r = m
            elif arr[m] > arr[r]:  # 说明答案不在 `[l,m]`，置 `l = m + 1`
                l = m + 1
            else:  # 说明答案在 `[l,r-1]`，置 `r -= 1`
                r -= 1
        
        return arr[l]