💬 Discord
Sign In
NeetCode #284LC-153MediumBinary SearchBlind 75NC 150NC 250
← Back to All Problems

#284 · #153 · Find Minimum in Rotated Sorted Array(寻找旋转排序数组中的最小值)

📌 Problem Statement & Constraints

Suppose an array of distinct integers sorted ascending is rotated between 1 and n times. Given the rotated array nums, return its minimum element. Constraints: 1 <= n <= 5000, -5000 <= nums[i] <= 5000, all values distinct. The follow-up asks for O(log n).

💡 Core Algorithmic Approaches

  1. Compare the middle element with the rightmost element. If nums[mid] > nums[right], the minimum lies strictly to the right of mid.
  2. Otherwise the minimum is at mid or to its left, so shrink the right bound to mid.
  3. Using the rightmost element (rather than the leftmost) is what makes the comparison unambiguous in the rotated array.
  4. The loop ends when lo == hi, which is the index of the minimum.

💻 Benchmark Python3 Implementation

class Solution:
    def findMin(self, nums: List[int]) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > nums[hi]:   # minimum is to the right
                lo = mid + 1
            else:                      # minimum is at mid or to the left
                hi = mid
        return nums[lo]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n): the search space halves each iteration.
💾 Space Complexity
O(1): three indices.

⚠️ Interview Pitfalls & Follow-ups

  • Comparing with nums[lo] instead of nums[hi]: with the leftmost element the comparison does not distinguish the two halves as cleanly, and the boundary conditions become subtle.
  • Using hi = mid - 1: that could skip the minimum; use hi = mid.
  • Returning nums[mid] when the loop ends: the loop ends at lo == hi, which is the minimum index.
  • Assuming the array is rotated at least once: an unrotated (already sorted) array is handled correctly, since the comparison always shrinks the right bound.