LeetCode 154. 寻找旋转排序数组中的最小值 II

Categories:

题目描述
思路分析
1. 解法一：二分查找（推荐）
相似题目

题目描述

✅ 154. 寻找旋转排序数组中的最小值 II

思路分析

解法一：二分查找（推荐）

核心思路：

本题是 153. 寻找旋转排序数组中的最小值的进阶版本，数组中允许出现重复元素。

维护左右指针 left 和 right，每次取中点 mid = left + (right - left) / 2。

比较 nums[mid] 与 nums[right]，分三种情况：

nums[mid] > nums[right]：最小值一定在 mid 右侧，令 left = mid + 1。

nums[mid] < nums[right]：最小值在 mid 或 mid 左侧，令 right = mid。

nums[mid] == nums[right]：无法判断最小值在哪侧（这是与 153 的核心区别），只能保守地令 right-- 缩小右边界，不会错过最小值（因为即使 nums[right] 是最小值，nums[mid] 也等于它，可以继续找）。

循环结束时 left == right，即为最小值下标。

最坏情况：数组全部相同（如 [1,1,1,1,1]），每次只能 right--，退化为 O(n)。

复杂度分析：

时间复杂度：O(log n)，其中 n 为数组长度；最坏情况（全部重复元素）退化为 O(n)

空间复杂度：O(1)，只使用常数级别的额外空间

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            // 中间值大于右边值，最小值一定在 mid 右侧
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                // 中间值小于右边值，最小值在 mid 或 mid 左侧
                right = mid;
            } else {
                // nums[mid] == nums[right]，无法判断方向，保守缩小右边界
                right--;
            }
        }

        return nums[left];
    }
}

func findMin(nums []int) int {
	left, right := 0, len(nums)-1

	for left < right {
		mid := left + (right-left)/2

		// 中间值大于右边值，最小值一定在 mid 右侧
		if nums[mid] > nums[right] {
			left = mid + 1
		} else if nums[mid] < nums[right] {
			// 中间值小于右边值，最小值在 mid 或 mid 左侧
			right = mid
		} else {
			// nums[mid] == nums[right]，无法判断方向，保守缩小右边界
			right--
		}
	}

	return nums[left]
}

相似题目

题目	难度	考察点
153. 寻找旋转排序数组中的最小值	中等	二分查找 / 无重复元素
33. 搜索旋转排序数组	中等	二分查找 / 旋转数组
81. 搜索旋转排序数组 II	中等	二分查找 / 含重复元素
34. 在排序数组中查找元素的第一个和最后一个位置	中等	二分查找 / 边界查找
852. 山脉数组的峰顶索引	中等	二分查找 / 峰值
162. 寻找峰值	中等	二分查找 / 峰值

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/03541721