HARD Lab · Binary Search · 08

153. Find Minimum in Rotated Sorted Array

A sorted array was rotated at some unknown pivot — binary search still works in O(log n) by comparing nums[mid] to nums[hi] (not nums[lo]) to reliably decide which half holds the minimum.

● MediumBinary SearchTypeScript

PROBLEM What we're solving

Given an array of distinct integers that was originally sorted in ascending order and then rotated at some unknown pivot, return the minimum element. You must run in O(log n).

Example: [4, 5, 6, 7, 0, 1, 2] was rotated from [0, 1, 2, 4, 5, 6, 7]. The answer is 0at index 4. A linear scan would work but costs O(n) — the O(log n) constraint forces binary search.

KEY IDEA Compare nums[mid] to nums[hi] to locate the inflection

Insight →In a rotated sorted array, one half is always “normal” (ascending) and the other contains the rotation point. Comparing nums[mid] to nums[hi] tells you which half is normal: if nums[mid] > nums[hi], the left half is the larger segment and the minimum must be in the right half; otherwise the minimum is at mid or in the left half.

Classic confusion → Many learners instinctively compare nums[mid] to nums[lo]. This breaks on unrotated arrays (e.g. [1,2,3]) because nums[lo] is always ≤ nums[mid] in the unrotated left half, giving no information about which side to discard. Always anchor to nums[hi].

RECIPE Binary search anchored to the right boundary

0 · Initialize. lo = 0, hi = nums.length - 1. Loop while lo < hi.
1 · Compute mid. mid = ⌊(lo + hi) / 2⌋.
2 · Compare to right boundary. If nums[mid] > nums[hi], the minimum is strictly to the right of mid — set lo = mid + 1.
3 · Otherwise. nums[mid] ≤ nums[hi] means mid might be the minimum or the minimum is left — set hi = mid(include mid, don't skip it).
4 · Converge. When lo === hi, both pointers sit on the minimum. Return nums[lo].

COST Complexity & alternatives

Linear scan

O(n)

Simple but misses the sorted-array structure entirely.

Binary search

O(log n)

O(1) space; exploits the partial-sort structure.

Space is O(1) — only three integer pointers. No auxiliary structure needed.

Pattern transfer → The same comparison strategy powers Search in Rotated Sorted Array (LC 33 — find a target, not just the minimum), Find Minimum in Rotated Sorted Array II (LC 154 — with duplicates, worst-case O(n)), and Find Peak Element(LC 162 — similar “which slope am I on?” logic). Any time a sorted invariant is partially broken, binary search with a boundary comparison rescues O(log n).

RUN IT Compare nums[mid] to nums[hi] — not nums[lo]

nums =

step 0 / 8

STARTBinary search on a rotated sorted array. lo=0, hi=6. We compare nums[mid] to nums[hi] (not nums[lo]) — this is the key insight.

nums4lo51627304152hi

State

—

mid

—

cmp

lomidhiminimum found

slowfast

TYPESCRIPT The solution, annotated

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

  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);

    if (nums[mid] > nums[hi]) {
      // mid is in the left (larger) segment — min is to the right
      lo = mid + 1;
    } else {
      // mid is in the right (smaller) segment — min is at mid or left
      hi = mid;
    }
  }

  return nums[lo]; // lo === hi — the minimum
}

Reading it block by block

Lines 2–3 — set up the window. lo and hi bracket the entire array. The loop invariant is that the minimum always lives in [lo, hi] (inclusive).

Line 5 — loop condition lo < hi. When the window collapses to one element (lo === hi), that element must be the minimum by the invariant — we exit and return it. Using < (not ≤) prevents an off-by-one infinite loop when lo === hi.

Lines 9–12 — the critical comparison. If nums[mid] > nums[hi], the rotation point lies to the right of mid, so the minimum is also to the right. We safely discard the left half by setting lo = mid + 1(mid itself is definitely not the minimum when it's greater than the rightmost element in range).

Lines 13–15 — otherwise close hi. nums[mid] ≤ nums[hi] means the right half is properly ordered and mid could be the minimum. We set hi = mid rather than hi = mid - 1 to preserve mid as a candidate. This is why the search terminates: mid = ⌊(lo+hi)/2⌋ < hi whenever lo < hi, so hi strictly decreases.

Line 19 — return the converged pointer. The loop exits with lo === hi. By the invariant the minimum is in the window — and a window of size 1 has only one choice.

Complexity → O(log n) time — each iteration halves the search window. O(1) space — only lo, hi, and mid are tracked.

INTERVIEWFollow-ups they'll ask

“What if duplicates are allowed?” LC 154. When nums[mid] === nums[hi]you can't tell which half is normal, so you must shrink with hi--. Worst case degrades to O(n).
“Can you find an arbitrary target instead?” Yes — LC 33. After determining which half is sorted, check whether the target falls in that half; if so, search there, otherwise flip.
“What if the array was not rotated at all?” The algorithm handles it correctly — nums[mid] ≤ nums[hi] always, so hi walks left until lo === hi === 0.
“Why not compare to nums[lo]?” nums[lo] ≤ nums[mid] is always true in the unrotated left half, so it gives no signal about where the minimum is. The right boundary nums[hi] is the reliable anchor.
“Brute force?” A single linear scan — O(n) time, O(1) space. Mention it, then explain that the partial-sort structure lets us do better via binary search.

MNEMONIC The one-liner

"If mid is bigger than the right wall, the drop is to the right — else close from the right."

TRIGGERS When you see _ → reach for _

rotated sorted array, find minimum	binary search vs nums[hi]
nums[mid] > nums[hi]	lo = mid + 1 (min is right)
nums[mid] ≤ nums[hi]	hi = mid (mid may be the min)
sorted + partially broken invariant	binary search with right-boundary anchor

SKELETON The reusable shape

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

  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] > nums[hi]) {
      lo = mid + 1;   // min is RIGHT of mid
    } else {
      hi = mid;       // min is at mid or LEFT
    }
  }

  return nums[lo];
}

FLASHCARDS Tap to flip

Why compare nums[mid] to nums[hi] instead of nums[lo]?

nums[lo] ≤ nums[mid] is always true in the unrotated left segment — it gives no information. nums[hi] reveals which half contains the rotation point.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 7

QUESTION 01

What is the time complexity of the binary-search solution for findMin?

QUESTION 02

Given [4, 5, 6, 7, 0, 1, 2], what is the first value of mid and which pointer moves?

QUESTION 03

Why should you NOT compare nums[mid] to nums[lo]?

QUESTION 04

When nums[mid] ≤ nums[hi] you set hi = mid, not hi = mid - 1. Why?

QUESTION 05

What is the loop condition, and why not lo ≤ hi?

QUESTION 06

What changes when duplicates are allowed (LC 154)?

QUESTION 07

For [1, 2, 3, 4, 5] (no rotation), does the algorithm still return the correct answer?

PROBLEM What we're solving

KEY IDEA Compare nums[mid] to nums[hi] to locate the inflection

RECIPE Binary search anchored to the right boundary

COST Complexity & alternatives

RUN IT Compare nums[mid] to nums[hi] — not nums[lo]

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _