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

旋转过的升序数组，最小值藏在哪

给一个原本升序、元素互不相同的数组，前面一段整体挪到末尾（这叫旋转），问最小的数是几。题面 nums=[4,5,6,7,0,1,2] 就是升序 [0,1,2,4,5,6,7] 把 [0,1,2] 挪到末尾，最小值 0 在下标 4。题目卡死时间 O(log n)，逼你别硬扫一遍。

扫一遍就能找到，为什么还要费劲二分

笨办法是从头扫一遍、把见过的最小值记住，n 次比较、O(n)（n 是数组长度）。可这没用上『数组本来有序』，把它当乱数处理了。题目要 O(log n)，每步得砍掉一大片、不能逐格挪，这就得靠二分查找；只是数组被旋转过、不再整体递增，普通二分找 target 那套不能照抄。

转过一圈的数组，凭什么还能二分

旋转后不再整体升序，但结构规整：从断裂处劈成两段，每段各自升序，且前段每个数都比后段大。题面里 [4,5,6,7] 是偏大前段、[0,1,2] 是偏小后段，交界那个 0 就是最小值。随便挑一个位置，它落在哪段都判得出来——拿它跟一个固定参照比大小即可。归属可判、答案又卡在交界，就能用二分把范围往交界处夹。

中点为什么跟最右端比，而不是最左端

二分维护左右边界 l、r，每轮取中点 mid（当前范围正中间那个下标，mid=(l+r)//2）。命门是拿 nums[mid] 跟谁比：这里比最右端 nums[r]，不比最左端——数组转过时最右端始终在偏小的后段，当参照最稳。nums[mid]>nums[r] 说明 mid 在偏大前段，最小值在右边，左半连 mid 丢掉，l=mid+1；否则 mid 在偏小后段，最小值就是 mid 或在它左边，r=mid 把 mid 留着（它可能正是最小值）。比最左端则参照不稳、分不清 mid 在哪段。

把 [4,5,6,7,0,1,2] 从两头往中间夹

起手 l=0、r=6。第 1 轮 mid=3，nums[3]=7 大于最右端 nums[6]=2，mid 在前段，l=mid+1=4，缩到 [4,6]。第 2 轮 mid=5，nums[5]=1 不大于 nums[6]=2，mid 在后段，r=mid=5、留着 mid，缩到 [4,5]。第 3 轮 mid=4，nums[4]=0 不大于 nums[5]=1，r=mid=4，缩到 [4,4]。l 与 r 在下标 4 撞上，返回 nums[4]=0。

开闭区间配错，末格会一直空转

循环条件得用 while l<r：收缩靠 r=mid 保留了 mid，写成 l<=r 会在 l==r 时还进循环、取 mid=l 令 r=mid=l，边界一步不动、末格空转成死循环。偏小侧也只能 r=mid，写成 r=mid-1 会漏掉可能正是最小值的 mid、把答案跳过去。mid 则用 l+(r-l)//2 代替 (l+r)//2 更稳，数组极大时 l+r 相加不会顶破整数上限。整个过程每轮砍掉一半，最多约 log₂n 轮夹到一格，时间 O(log n)；只用 l、r、mid 三个下标，空间 O(1)。

Python

def findMin(nums):
    l, r = 0, len(nums) - 1
    while l < r:                  # 范围多于一格就继续二分
        mid = (l + r) // 2
        if nums[mid] > nums[r]:   # mid 在偏大的前段
            l = mid + 1           # 最小值在右半，丢掉左半+mid
        else:                     # mid 在偏小的后段
            r = mid               # 最小值在 mid 这边或左边，保留 mid
    return nums[l]                # l==r，落在最小值上

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 r = mid;
    }
    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 r = mid;
    }
    return nums[l];
}