寻找旋转排序数组中的最小值 II 图解题解

旋转又带重复的数组里，要挖出哪个数

给一个升序数组，从某处整体转一下、后半段挪到前面接上，可能含重复数字，得到 nums，找里面最小的那个。升序被掰断再接起来，断裂那道『断崖』下面就是最小值。题面 nums=[4,0,0,1,1,1,1,2,3,3,3,3,4]，最小值 0 被转到了中间那段的开头。

从头扫一遍也能找到，可惜白扫大半截

最直接是从头比到尾、记住最小数，n 个数扫 n 次，时间 O(n)。可这数组大半截还有序，挨个看把二分能省的一半也翻了遍，数到几万个就没必要。

盯着中点和右端比，怎么就知道最小值躲哪半

把中点 nums[mid] 和右端 nums[r] 比。nums[mid] 大于 nums[r]，中点还在前半那段大数里，最小值在它右边；nums[mid] 小于 nums[r]，中点已落进后半小数段，最小值在它左边、或就是它。

为什么盯右端不盯左端？和右端比三种大小方向干净；换成和左端比，大数段压在左边，方向反而容易判反。

相等时把右端退一格，为什么不会把最小值丢掉

两个指针 l、r 圈住还没排除的范围，起初 l=0、r=n-1。每轮取 mid=(l+r)//2 和 nums[r] 比：nums[mid] 大于 nums[r]，最小值在右半，l 跳到 mid+1；nums[mid] 小于 nums[r]，最小值在左半含中点，r 收到 mid（中点可能正是答案不能丢）。缩到 l、r 撞上，那格就是最小值。

麻烦全在相等：nums[mid] 等于 nums[r] 时，最小值在左在右都可能，方向判不出来。这时只把右端退一格（r-=1），凭什么不怕丢答案？因为右端 nums[r] 有中点 nums[mid] 这个一样的替身，中点还在 [l, r-1] 里。就算最小值恰好在 nums[r] 这格，答案要的是那个数值而非下标，丢掉它、同样大的中点还在，一分没少。绝不能跳半边：写成 nums[mid] 大于等于 nums[r] 就 l=mid+1，碰上 [1,0,1,1,1] 会跨过真正的 0。

题面这串数逐格收窄，l 和 r 一步步逼上去

起点 l=0、r=12。mid=6，nums[6]=1 小于 nums[12]=4，r 收到 6。r=6 时 mid=3，nums[3]=1 等于 nums[6]=1，右端退一格到 5。r=5 时 mid=2，nums[2]=0 小于 nums[5]=1，r 收到 2。r=2 时 mid=1，nums[1]=0 等于 nums[2]=0，右端退到 1。r=1 时 mid=0，nums[0]=4 大于 nums[1]=0，l 跳到 1。此刻 l、r 同停在 1，返回 nums[1]=0。

重复太多时，二分会退化成一格一格挪

正常每轮砍一半，时间 O(log n)、空间 O(1)。但相等分支每次只让 r 退一格，遇上 [2,2,2,2] 全重复，每轮才缩一格，最坏退化成 O(n)。

易错点也绕着相等打转：图快跳半边不写 r-=1，答案会丢在跳过的那半；比较对象错拿左端 nums[l]，方向就反；收缩得写 r=mid 而非 mid-1，中点自己可能就是最小值，退过头会漏掉它。

Python

def findMin(nums):
    l, r = 0, len(nums) - 1
    while l < r:
        mid = (l + r) // 2
        if nums[mid] > nums[r]:   # 中点比右端大
            l = mid + 1           # 最小值在右半
        elif nums[mid] < nums[r]: # 中点比右端小
            r = mid               # 最小值在左半(含中点)
        else:                     # 相等，分不清
            r -= 1                # 右端是替身，退一格
    return nums[l]

C++

int findMin(vector<int>& nums){
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (nums[mid] > nums[r]) l = mid + 1;
        else if (nums[mid] < nums[r]) r = mid;
        else r -= 1;
    }
    return nums[l];
}

Java

public int findMin(int[] nums) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (nums[mid] > nums[r]) l = mid + 1;
        else if (nums[mid] < nums[r]) r = mid;
        else r -= 1;
    }
    return nums[l];
}