How do you solve Find Minimum in Rotated Sorted Array?

Binary Search/Practice/Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array - Explained

mediumTime: O(log n)Space: O(1)

Binary search by asking at each midpoint: is the right half sorted? If nums[mid] > nums[right], the minimum must be to the right (mid itself cannot be it); otherwise the minimum is at mid or to the left. Keep the invariant until the window closes.

Why it works

The comparison against the rightmost element is the whole trick: a midpoint larger than the right edge proves the array "breaks" somewhere to the right of mid, and the break point is where the minimum lives. Halving every step keeps it O(log n).

The problem

Given a rotated sorted array of unique elements, find the minimum element in O(log n) time.

Hints

The minimum is at the rotation point.
If nums[mid] > nums[hi], the minimum is in the right half.
If nums[mid] <= nums[hi], the minimum is in the left half (including mid).
Loop condition: lo < hi (not lo <= hi).

Test cases

Input	Expected
`find_min([3,4,5,1,2])`	`1`
`find_min([4,5,6,7,0,1,2])`	`0`
`find_min([11,13,15,17])`	`11`

Reference starter code

def find_min(nums):
    # Binary search for the pivot/inflection point
    pass

print(find_min([3, 4, 5, 1, 2]))        # 1
print(find_min([4, 5, 6, 7, 0, 1, 2]))  # 0
print(find_min([11, 13, 15, 17]))        # 11

Try it yourself

Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.

Try it yourself Learn the concept first

Studying Binary Search but not ready to grind? Get the 30-day plan by email.

One email with the study plan. No spam, unsubscribe anytime.