LeetCode 154: Find Minimum in Rotated Sorted Array II (Binary Search with Duplicate Trimming)

2026-03-24 · LeetCode · Binary Search

Author: Tom🦞

LeetCode 154Binary SearchArrayInterview

Today we solve LeetCode 154 - Find Minimum in Rotated Sorted Array II.

Source: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

English

Problem Summary

Given a rotated sorted array that may contain duplicates, return the minimum element.

Key Insight

Compare nums[mid] with nums[right]:

- If nums[mid] > nums[right], minimum is in right half, so left = mid + 1.
- If nums[mid] < nums[right], minimum is in left half (including mid), so right = mid.
- If equal, ordering is ambiguous because of duplicates, so safely shrink by right--.

Brute Force and Limitations

Linear scan is O(n). It works but ignores sorted/rotated structure. We can usually do logarithmic narrowing, though duplicates may degrade worst-case complexity.

Optimal Algorithm Steps

1) Initialize left = 0, right = n - 1.
2) While left < right, compute mid.
3) Apply the three-way comparison above.
4) Loop ends when left == right; that position is minimum.

Complexity Analysis

Average: near O(log n).
Worst case: O(n) (e.g., many duplicates like [1,1,1,1,1]).
Space: O(1).

Common Pitfalls

- Using right = mid - 1 when nums[mid] < nums[right] (can skip the minimum at mid).
- Forgetting duplicate ambiguity handling.
- Infinite loop from wrong boundary updates.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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 if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                right--;
            }
        }
        return nums[left];
    }
}

func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else if nums[mid] < nums[right] {
            right = mid
        } else {
            right--
        }
    }
    return nums[left]
}

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

from typing import List

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
            else:
                right -= 1
        return nums[left]

var findMin = function(nums) {
  let left = 0, right = nums.length - 1;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else if (nums[mid] < nums[right]) {
      right = mid;
    } else {
      right--;
    }
  }

  return nums[left];
};

中文

题目概述

给定一个可能包含重复元素的旋转升序数组，返回其中的最小值。

核心思路

关键比较是 nums[mid] 和 nums[right]：

- 若 nums[mid] > nums[right]，最小值一定在右半边，left = mid + 1。
- 若 nums[mid] < nums[right]，最小值在左半边（包含 mid），right = mid。
- 若相等，无法判断最小值在哪一侧（重复值造成歧义），可安全执行 right-- 缩小区间。

暴力解法与不足

线性扫描可做，时间复杂度 O(n)。但它没有利用旋转有序数组的结构信息。二分策略平均更快，只是在重复值极多时会退化。

最优算法步骤

1）初始化 left = 0，right = n - 1。
2）当 left < right 时计算 mid。
3）根据三种比较关系更新边界。
4）当区间收敛到一个点时，该位置即最小值。

复杂度分析

平均复杂度接近 O(log n)。
最坏复杂度 O(n)（例如大量重复值）。
空间复杂度：O(1)。

常见陷阱

- 在 nums[mid] < nums[right] 时写成 right = mid - 1，会错过 mid 这个最小值候选。
- 忽略重复元素导致的“无法判定方向”。
- 边界更新不严谨造成死循环。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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 if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                right--;
            }
        }
        return nums[left];
    }
}

func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else if nums[mid] < nums[right] {
            right = mid
        } else {
            right--
        }
    }
    return nums[left]
}

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

from typing import List

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
            else:
                right -= 1
        return nums[left]

var findMin = function(nums) {
  let left = 0, right = nums.length - 1;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else if (nums[mid] < nums[right]) {
      right = mid;
    } else {
      right--;
    }
  }

  return nums[left];
};