LeetCode 每日一题笔记

0. 前言

• 日期：2026.05.15
• 题目：153. 寻找旋转排序数组中的最小值
• 难度：中等
• 标签：数组、二分查找

1. 题目理解

问题描述： 给定一个无重复元素的升序数组，经过1~n次旋转后，找出并返回数组中的最小元素。 要求时间复杂度为 $O(\log n)$。

示例：

输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5]，旋转3次得到输入数组，最小值为1。

输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7]，旋转4次得到输入数组，最小值为0。

2. 解题思路

核心观察

• 旋转后的数组可分为两个有序子数组，最小值就是右半部分的第一个元素；
• 利用二分查找，通过比较 arr[mid] 和 arr[right]，判断最小值所在区间：
  • arr[mid] > arr[right]：说明最小值在 mid 的右侧（含 mid+1）；
  • arr[mid] <= arr[right]：说明最小值在 mid 的左侧（含 mid）。

算法步骤

1. 初始化左右指针 left = 0，right = nums.length - 1；
2. 循环直到 left == right：
   • 计算 mid = left + (right - left) / 2；
   • 比较 arr[mid] 与 arr[right]，移动指针缩小范围；
3. 返回 nums[left]（或 nums[right]），即为最小值。

3. 代码实现

package lc100_lc199.lc153;

class Solution {
    int binary(int[] arr, int left, int right) {
        while (left != right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > arr[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return arr[left];
    }

    public int findMin(int[] nums) {
        return binary(nums, 0, nums.length - 1);
    }
}

4. 代码优化说明

减少分支判断，直接将逻辑合并到主函数中，去掉单独的 binary 方法：

package lc100_lc199.lc153;

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

5. 复杂度分析

• 时间复杂度：$O(\log n)$ 二分查找每次将区间减半，最多执行 ${\log }_{2}n$ 次循环。
• 空间复杂度：$O(1)$ 仅使用常数级额外变量，无递归栈或额外数组开销。

6. 总结

• 核心思路：二分查找，利用旋转数组的局部有序性定位最小值；
• 关键判断：通过 arr[mid] 与 arr[right] 的大小关系，快速确定最小值所在区间；
• 优化后代码逻辑更紧凑，去掉了不必要的方法调用，可读性和效率更高。