Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array takes a sorted array that someone "spun" around a hidden point and asks you to find the smallest value — in O(log n). It is a sharp lesson in modified binary search: you are not searching for a value, you are searching for the rotation point.

The slow way first

The obvious answer is to scan every element and track the smallest — that is O(n). It works, but it throws away the structure we were given. The array is almost sorted; binary search should still apply. The challenge says O(log n), so a linear scan is not the intended solution.

The idea: search for the rotation point

The minimum is the only element smaller than the one before it — the seam where the array wraps around. To locate that seam with binary search, look at the middle element and ask one question: is nums[mid] bigger than nums[hi]?

• If nums[mid] > nums[hi], the right half is "out of order," so the seam (the min) must be to the right of mid. Move lo = mid + 1.
• Otherwise nums[mid] <= nums[hi], meaning the right half from mid onward is sorted, so the min is mid itself or to its left. Move hi = mid (keep mid — it could be the answer).

Compare against nums[hi], not nums[lo]. Comparing to the right end is what makes the two cases clean: hi = mid (not mid - 1) because mid might be the minimum.

Walk through it

Step through the animation with nums = [3, 4, 5, 1, 2]. lo and hi bracket the array. First mid = 2 (value 5); since 5 > 2 the min is to the right, so lo jumps to 3. Next mid = 3 (value 1); since 1 <= 2 the min is at mid or left, so hi = mid = 3. Now lo == hi, the loop stops, and nums[lo] = 1 is the answer.

Pseudocode

lo, hi = 0, last index
while lo < hi:
    mid = (lo + hi) // 2
    if nums[mid] > nums[hi]:     # right half is rotated
        lo = mid + 1              # min is strictly to the right
    else:                        # right half (from mid) is sorted
        hi = mid                 # min is mid or to its left -- keep mid
return nums[lo]                  # lo == hi points at the minimum

The Python solution

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

• The loop condition is lo < hi (not <=): we shrink the window until a single element remains.
• We compare nums[mid] to nums[hi] — the right end — which cleanly tells us which half holds the seam.
• lo = mid + 1 discards mid because, being larger than nums[hi], it cannot be the minimum.
• hi = mid keeps mid because it might be the minimum itself.
• When the loop ends, lo == hi and nums[lo] is the answer — no separate "found" check needed.

Complexity

Each iteration throws away half the remaining elements, so we finish in about log n steps using only two index variables.

When this pattern shows up

Practice