Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumbinary-search

Find Minimum in Rotated Sorted Array

Problem (restated)

A sorted array of unique values was rotated. Find the minimum element in O(log n).

Intuition

The minimum is the only place where order “breaks.” Compare mid with the right end to decide which half is sorted.

Approaches

Binary search on rotation

Unverified

Time O(log n)Space O(1)

Idea. If nums[mid] > nums[hi], min is to the right; else min is at mid or left.

Walkthrough. [3,4,5,1,2] → mid=5 > 2 → search right → min=1.

Trade-offs. Linear min scan is simpler but fails log-time requirement.

Solution

export function findMin(nums: number[]): number {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid]! > nums[hi]!) lo = mid + 1;
    else hi = mid;
  }
  return nums[lo]!;
}

export function findMin(nums: number[]): number {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid]! > nums[hi]!) lo = mid + 1;
    else hi = mid;
  }
  return nums[lo]!;
}

Template connection

Rotated-array binary search: the minimum sits on the unsorted side.

Reflection

The minimum is the rotation break. If nums[mid] > nums[hi], the minimum is on the right. Why not on the lo side?
An unrotated array’s minimum is nums[0]. A single element is itself.
No duplicates here. Why does equality need its own care on LC 154?