Find Minimum in Rotated Sorted Array

Given a sorted array that has been rotated at an unknown pivot, return the minimum element. The array contains no duplicates.

Why this is worth learning

The right endpoint identifies which side of the rotation contains the minimum. A midpoint greater than that endpoint lies in the high segment before the minimum.

Before coding: one-minute experiment

For [3,4,5,1,2], what does comparing midpoint 5 with right endpoint 2 prove? Why is hi=mid-1 wrong in the other branch?

Function signature

func FindMin(nums []int) int

Inputs / outputs

• nums: rotated sorted array with distinct elements.
• Return: the minimum value.

Example

nums = [4,5,6,7,0,1,2]
Output: 0

Constraints

• 1 <= len(nums) <= 100_000

Core idea (near-solution)

A scan finds the minimum without using the rotation promise. To eliminate half at once, compare the midpoint with the right endpoint. If the midpoint is larger, a wrap must occur after it; otherwise the midpoint may already be the smallest value in the retained low segment. That last possibility explains why the second branch must keep mid rather than discard every inspected element.

Binary search by comparing nums[mid] with nums[hi] to decide which side contains the minimum.

Invariant: the minimum is always within the current [lo, hi] range.

Algorithm (step-by-step)

1. Set lo = 0, hi = len(nums) - 1.
2. While lo < hi:
   • mid = lo + (hi-lo)/2.
   • If nums[mid] > nums[hi], the minimum is to the right: lo = mid + 1.
   • Else the minimum is at mid or to the left: hi = mid.
3. Return nums[lo].

Correctness sketch

The minimum is inside [lo,hi]. If nums[mid]>nums[hi], the pivot and minimum must lie strictly after mid, so lo=mid+1 is safe. Otherwise the subarray from mid through hi is in the low sorted segment or the whole interval is unrotated; mid may itself be the minimum, so retaining it with hi=mid is necessary. Distinctness prevents equality ambiguity except when mid=hi, which the loop excludes. Each step decreases the interval length, and the final index is the unique minimum position.

Trace (hand walkthrough)

Example input:
nums = [4,5,6,7,0,1,2]
Output: 0

Walk:
- lo=0 hi=6 mid=3 val=7 > nums[hi]=2 -> lo=4
- lo=4 hi=6 mid=5 val=1 <= nums[hi]=2 -> hi=5
- lo=4 hi=5 mid=4 val=0 -> hi=4 => min=0

Pitfalls to avoid

• Using >= instead of > in the comparison (can skip the minimum when no duplicates).
• Forgetting the already-sorted case (the loop handles it naturally).

Debugging lens

Test a minimum at every position and the length-one case. Do not borrow duplicate-tolerant rules without changing the stated complexity and proof.

Complexity

• Time: O(log n).
• Extra space: O(1).

Implementation notes (Go)

• Use indices; no extra arrays are needed.

Reconstruction checkpoint

For [3,4,5,1,2], what does comparing midpoint 5 with right endpoint 2 prove? Why is hi=mid-1 wrong in the other branch?

Return to Binary Search · Module quiz