LeetCode 153 - Find Minimum in Rotated Sorted Array

This Medium problem asks for the minimum value in a sorted array that has been rotated once and contains no duplicates. I compared the middle value with the right boundary and reduced the candidate interval until both boundaries met.

---

Problem link and explanation

• Problem: 153. Find Minimum in Rotated Sorted Array
• Summary: Given a rotated array of distinct values that was originally sorted in ascending order, return its minimum in O(log n) time.

For example, [4, 5, 6, 7, 0, 1, 2] consists of two ascending segments. The minimum is at the rotation boundary where the values drop, and binary search can locate that boundary by determining which half still contains it.

---

Approach

The left and right indices define an interval that must contain the minimum. Each iteration calculates its middle index.

pivot = left + (right - left) // 2

If nums[pivot] is smaller than nums[right], the segment from pivot through right is sorted. The minimum is either at pivot or somewhere to its left, so pivot must remain in the candidate interval.

if nums[pivot] < nums[right]:
    right = pivot

If nums[pivot] is greater than nums[right], the rotation boundary lies strictly to the right of pivot. The middle index cannot be the minimum and can be discarded.

else:
    left = pivot + 1

When left and right meet, their shared index is the only remaining candidate.

---

Troubleshooting

My first attempt compared nums[left] with nums[right] to choose a direction. That comparison does not reliably identify which half around the middle contains the minimum. Both boundaries can belong to portions whose relationship changes as the interval narrows, and the left value alone does not justify discarding either side of the middle.

Comparing nums[pivot] with nums[right] gives the required invariant. A smaller middle value means the right portion is sorted and the minimum is at the middle or to its left. A larger middle value proves that the rotation boundary is to the right, so the middle can be removed.

---

Complexity analysis

• Time complexity: O(log n)
  • Each iteration removes about half of the remaining candidate interval.
• Space complexity: O(1)
  • Only the left, right, and middle indices are stored.

---

Implementation code

from typing import List

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1

        while left < right:
            pivot = left + (right - left) // 2

            if nums[pivot] < nums[right]:
                right = pivot
            else:
                left = pivot + 1

        return nums[right]

---

Summary and reflection

Binary search needs a comparison that proves which interval can be discarded. Comparing the middle with the right boundary identifies whether the rotation point remains to the right, while preserving the middle when it may itself be the minimum. That invariant reduces the search interval without losing the answer.