Find Minimum in Rotated Sorted Array

The problem

Array sorted ascending, then rotated at unknown pivot. All values unique. Find the minimum element in O(log n).

[3,4,5,1,2] → 1
[4,5,6,7,0,1,2] → 0
[11,13,15,17] → 11  // rotation 0

Brute

function findMinBrute(nums: number[]): number {
  return Math.min(...nums);
}

Time	O(n)
Space	O(1)

Optimal: binary search on rotation

Invariant: min is always in [lo, hi].

Compare nums[mid] with nums[hi]:

• If nums[mid] > nums[hi] → min is strictly right of mid (lo = mid + 1)
• Else → mid could be min or min is left (hi = mid)

function findMin(nums: number[]): number {
  let lo = 0;
  let hi = nums.length - 1;

  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] > nums[hi]) lo = mid + 1;
    else hi = mid;
  }
  return nums[lo];
}

Time	O(log n)
Space	O(1)

Why not compare to nums[lo]?

When the subarray is already sorted (nums[lo] < nums[hi]), min is nums[lo] — works too, but mid vs hi is a clean single rule that handles the unrotated case (always shrink hi).

Walk [4,5,6,7,0,1,2]

lo	hi	mid	nums[mid] vs hi
0	6	3	7 > 2 → lo=4
4	6	5	1 < 2 → hi=5
4	5	4	0 < 1 → hi=4
done → 0

Edge cases

• Single element
• Already sorted (rotate 0)
• Min at index 0 or last
• Two elements

Follow-up: duplicates (LC 154)

When nums[mid] === nums[hi], you can’t tell side — hi-- (or lo++) carefully → O(n) worst.

Common mistakes

• Infinite loop: using hi = mid - 1 when mid might be answer
• Using < wrong and missing unrotated arrays
• Claiming O(log n) with duplicates without caveats

Interview delivery

1. Rotated sorted, unique.
2. Linear min baseline.
3. Binary search mid vs hi.
4. Trace unrotated.
5. O(log n).

Mental model

A rotated sorted array is two sorted runs. The minimum is the first element of the right run (or index 0 if unrotated). Binary search compares mid to the right end to learn which run mid sits in.

Invariants to state

• Search range always contains the minimum.
• When nums[mid] > nums[hi], min ∈ (mid, hi].
• Else min ∈ [lo, mid].

Using hi = mid not mid-1 is load-bearing.

Out-loud answer

“Rotated sorted unique elements, find min in log n. Binary search: if mid > hi, go right else shrink hi to mid. Loop until lo==hi. Unrotated arrays naturally return nums[0].”

Related

• Search in Rotated Sorted Array
• Binary Search
• Find Duplicate Number
• Two Sum
• JavaScript Interview Guide

Further reading

• LeetCode 153 — Find Minimum in Rotated Sorted Array
• Binary search