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.

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)

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

• Invariant: the minimum is always within the current [lo, hi] range.
• The valid answer lies within the maintained [lo, hi] range.
• Each comparison discards half the range that cannot contain an answer.
• When the loop ends, the remaining boundary/index is correct.

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).

Complexity

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

Implementation notes (Go)

• Use indices; no extra arrays are needed.