Find Minimum in Rotated Sorted Array: Rotated minimum Pattern

Learning Outcome

After this lesson, you should be able to find the rotation pivot by comparing the middle value with the right boundary.

Problem Statement

Given a rotated sorted array of unique elements, return the minimum element.

Brute Force Approach

Scan the array and track the smallest value. This is correct but costs O(n).

Optimized Approach

Compare nums[mid] with nums[right]. If nums[mid] > nums[right], the minimum must be to the right of mid. Otherwise, mid may be the minimum, so keep it by moving right = mid.

Exact Pseudocode

left = 0
right = length(nums) - 1
while left < right:
  mid = left + (right - left) // 2
  if nums[mid] > nums[right]:
    left = mid + 1
  else:
    right = mid
return nums[left]
  

Reference Code

class Solution:
    def findMin(self, nums):
        left = 0
        right = len(nums) - 1

        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid

        return nums[left]
  

Sample Dry Run

Complexity

Edge Cases

• Array is not rotated.
• Only one element.
• Minimum is at the last or first index.

Interview Checklist

• Compare with nums[right], not always with nums[left].
• Keep mid when it may be the minimum.
• Return nums[left] after convergence.

FAQs

It tells whether the middle is in the left sorted part or the right sorted part around the pivot.

You can add that optimization, but the boundary search already handles the not-rotated case cleanly.

Binary search for the rotation pivot.