leetcode leetcode 二分查找 旋转数组

旋转数组中的最小值

LeetCode 153 题解笔记

Posted by BY on April 26, 2026
CATALOG

    原文已经写了二分思路，这里把”旋转数组”的概念和判定原理补全。代码保留原样。

    题目背景

    LeetCode 153「寻找旋转排序数组中的最小值」。一个原本递增的数组在某个未知点被旋转过一次（如 [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]），数组元素互不相同，要求在 O(log n) 内找出其中的最小值。

    概念解释

    • 旋转数组：把一个有序数组从某下标处切开，前后两段交换位置后得到的数组。它由两段各自有序的子数组拼接而成，最小值就是后一段的起点。
    • 二分查找的关键：并不一定要”目标值有序”，只要能在 O(1) 时间内判断答案在哪一侧，就可以二分。

    实现原理

    每一轮拿 mid 与 h（区间右端值）比较：

    • nums[mid] < nums[h]：说明 [mid, h] 段是单调递增的，最小值不可能在 mid 右侧。再看 nums[mid-1] 是否大于 nums[mid]，如果是则 mid 就是分界点（最小值），否则收缩 h = mid - 1。
    • nums[mid] > nums[h]：说明断点在 (mid, h]，最小值一定在 mid 右侧，l = mid + 1。

    当 l == h 时收敛到最小值。注意原代码把”找到答案”的判断显式写在条件里，便于尽早返回。

    时间复杂度 O(log n)，空间复杂度 O(1)。本题元素互不相同，所以无需考虑 LeetCode 154 那种 nums[mid] == nums[h] 退化为线性扫描的情形。

    参考实现

    旋转数组中的最小值

    解题思路： 二分法： 1、判断，递增区间，从而判断，l 或 者 h的变化 2、 终止条件: 判断找到了最小值。

    class Solution {
public:
    int findMin(vector<int>& nums) {

        int l = 0;
        int h = nums.size() - 1;

        while(l < h)   // 这里是小于
        {
            int mid = l + (h - l)/2;  //防止溢出

            if(nums[mid] < nums[h])
            {
                if(mid ==l)       // mid == l ,找到了最小值
                {
                    return nums[mid];
                }else if(mid > l) // mid > l， 与左侧的值比较一下，判断是否需要继续二分
                {
                    if(nums[mid-1]> nums[mid])
                    {
                        return nums[mid];
                    }
                }
                h = mid - 1;
            }else if(nums[mid] > nums[h])
            {
                l = mid + 1;
            }
        }
        return nums[l];   //l ==h ，找到了最小值。
    }
};
    FEATURED TAGS
    Git Cheat Sheet Markdown Tools C++ Linker Thread Linux TCP Network GDB Debug leetcode 链表 WSL Ubuntu Windows Linux Kernel GCC Android adb Troubleshooting Profiling Sanitizer glibc MySQL Database Python curl Build ELF clang-format CMake Graphviz Performance vcpkg Protobuf 排查 速查 内存 STL 调试 性能分析 性能 读书笔记 方法论 架构 网络 Timer mbedTLS TLS 安全 负载均衡 脚本 工具 LRU 二叉树 BST 中序遍历 回溯 二分查找 优先队列 排序 旋转数组 jenkins 部署
    FRIENDS