Find Minimum in Rotated Sorted Array – Binary Search (LeetCode 153)

In this problem, we are given a rotated sorted array with unique elements. The goal is to find the minimum element in O(log n) time, which naturally points to a binary search based solution.

Key Observations

• A rotated sorted array always has one sorted half.
• If the array is not rotated, the first element is the minimum.
• The minimum element always lies in the unsorted half.

Approach

We use two pointers (s and e) and compare the middle element with the right boundary. Based on this comparison, we eliminate the sorted half and narrow the search space until both pointers converge.

Python Code

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

        while s < e:
            mid = (s + e) // 2

            if nums[mid] > nums[e]:
                s = mid + 1
            else:
                e = mid

        return nums[s]

    

Why This Works

If nums[mid] > nums[e], the minimum must be to the right of mid. Otherwise, it lies at mid or to the left. The loop ends when s == e, which points directly to the minimum element.

Time & Space Complexity

• Time Complexity: O(log n)
• Space Complexity: O(1)

Source Code

View the complete solution on GitHub: LC153 – Find Minimum in Rotated Sorted Array