Find Minimum in Rotated Sorted Array

BINARY SEARCH · MEDIUM

The problem

You’re given an array of unique integers that started out sorted in ascending order, then got “rotated” — cut at some pivot point and the front chunk moved to the back. [0,1,2,4,5,6,7] rotated 4 times becomes [4,5,6,7,0,1,2]: the first 4 elements got moved to the end. A rotation count of 0 is a valid input too — the array might already be in its original sorted order, never rotated at all. Given the rotated array, find the minimum element. Example: [3,4,5,1,2] → 1. [4,5,6,7,0,1,2] → 0. [11,13,15,17] → 11 (rotated 0 times — already sorted). The optimal solution must run in O(log n) time.

Solution 1: Brute force — linear scan for the minimum

The most direct reading of the problem completely ignores that the array used to be sorted: just walk every element once and keep whichever value is smallest so far, exactly like finding the minimum of any unsorted array. This is correct and simple, but it’s honestly not “brute force” in the sense of doing extra wasted work — it’s brute force in the sense of not exploiting the one piece of structure the problem hands you for free. The rotated array isn’t random: it’s two sorted runs glued together, and a linear scan never asks “where’s the seam?” — it just checks every value, one at a time, blind to that structure.

Interactive visualization

Tracing nums = [4, 5, 6, 7, 0, 1, 2] — the same rotated array verified against the code below.

nums = [4, 5, 6, 7, 0, 1, 2] — best approach: scan every element, track the running minimum

Press Play or Step to begin.

Step 0 / 8

The code

function findMinBrute(nums) {
  let min = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < min) {
      min = nums[i];
    }
  }
  return min;
}

Line by line:

min starts at nums[0] — correctly handles a single-element array on its own, with no special-casing needed.
The loop starts at i = 1 since index 0 is already accounted for by the initial value of min.
if (nums[i] < min) min = nums[i] is the entire algorithm — it’s the same “track the smallest value seen so far” pattern you’d use on any unsorted array. Nothing here reads or reacts to the fact that nums is two sorted runs stitched together.
Every index is visited exactly once, regardless of where the rotation seam actually is — that’s what keeps this at a flat O(n), but also what stops it from ever doing better than O(n).

Complexity

Time	Space	Approach
O(n)	O(1)	Linear scan, tracking the running minimum

Solution 2: Optimal — binary search on the rotation point

The rotated array is always exactly two sorted runs: a “high” run at the front and a “low” run at the back, glued at the rotation seam — and the minimum is always the very first element of that low run (or, if the rotation count was 0, it’s simply nums[0] and there’s no seam at all). Maintain lo/hi pointers spanning the whole array. At each step, compute mid = Math.floor((lo + hi) / 2) and compare nums[mid] against nums[hi] — always against hi, never against lo, because comparing against hi is what reliably tells you which half contains the seam:

If nums[mid] > nums[hi], then mid is sitting in the “high” run and the seam (and therefore the minimum) must be strictly to the right of it — narrow to lo = mid + 1.
Otherwise, nums[mid] <= nums[hi] means mid is already in the “low” run — it could even be the minimum itself, so it must stay in the search space: narrow to hi = mid, never mid - 1. Dropping mid from the window here is the classic off-by-one trap in this exact problem — see the Interview Corner below for a concrete case where it silently returns the wrong answer.

The loop continues until lo === hi; that single remaining index is the minimum.

Interactive visualization

Same array as Solution 1, nums = [4, 5, 6, 7, 0, 1, 2] — watch the search window shrink toward the rotation seam.

nums = [4, 5, 6, 7, 0, 1, 2] — binary search: compare mid against hi to find which half contains the seam

Press Play or Step to begin.

Step 0 / 8

The code

function findMinOptimal(nums) {
  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;
    } else {
      hi = mid;
    }
  }

  return nums[lo];
}

Line by line:

lo = 0, hi = nums.length - 1 — the window starts as the whole array, since the seam could be anywhere (including “nowhere,” if rotation count is 0).
while (lo < hi) — the loop keeps narrowing until exactly one index remains. It deliberately stops at lo === hi rather than lo <= hi, because the answer is a single index, not a range to keep searching inside.
nums[mid] > nums[hi] is the entire decision: if mid’s value is bigger than hi’s, mid is still in the untouched “high” run, and the seam has to be somewhere after it — so lo = mid + 1 safely discards mid, because it’s provably not the minimum (something smaller than it exists further right).
The else branch (nums[mid] <= nums[hi]) means mid is already in the “low” run — and specifically, it might be the smallest value in that run, so it can never be safely thrown away. Setting hi = mid (not mid - 1) keeps it in the window for the next iteration.
When the loop exits, lo === hi and that index is the minimum — return nums[lo].

Complexity

Time	Space	Approach
O(log n)	O(1)	Binary search on the rotation point, comparing mid against hi

Complexity comparison

Solution	Time	Space
Brute force (linear scan)	O(n)	O(1)
Optimal (binary search on the seam)	O(log n)	O(1)

This is a genuine asymptotic time improvement, not a constant-factor tweak — the linear scan inspects every element no matter what, while the binary search discards roughly half of the remaining search space on every single comparison, by using the one guarantee the rotation gives you: whichever half of the current window is “out of order” relative to itself is the half that contains the seam. Space stays O(1) on both sides.

Interview corner

Q: Why does the binary search always compare nums[mid] against nums[hi], and never against nums[lo]?

Comparing against hi gives an unambiguous answer every time: if nums[mid] > nums[hi], mid is definitely still in the unrotated “high” run, because a value can only be bigger than something later in the array if the array wrapped around somewhere between them.
Comparing against lo instead doesn’t reliably tell you that — when the array hasn’t rotated at all (or the window no longer straddles the seam), nums[mid] >= nums[lo] is just normal ascending order and carries no information about where the minimum is.
hi is the one endpoint that’s guaranteed to be on the “low” side of any seam that exists inside the current window, which is exactly the property the comparison needs.

Q: What actually breaks if you write hi = mid - 1 instead of hi = mid in the “not greater” branch?

Take nums = [3, 0, 1, 2] (rotated version of [0,1,2,3]). The correct minimum is 0 at index 1.
Step through it: lo=0, hi=3, mid=1. nums[1]=0, nums[3]=2. Since 0 is not greater than 2, the “not greater” branch runs — and mid = 1 is exactly the index holding the true minimum.
With the buggy hi = mid - 1, the window becomes lo=0, hi=0 — index 1 (the actual answer) is thrown away, and the loop immediately returns nums[0] = 3, which is wrong. With the correct hi = mid, the window becomes lo=0, hi=1, keeping index 1 in play, and the next comparison correctly narrows down to it.
The rule to remember: mid can only be safely discarded on the branch that proves it isn’t the answer (nums[mid] > nums[hi]). On the other branch, mid hasn’t been ruled out — it might BE the answer — so it must stay in the window.

↳ Common follow-up: “What if there were duplicate values allowed?” This problem guarantees unique integers specifically so that nums[mid] > nums[hi] (strict inequality) is always decisive. With duplicates, nums[mid] === nums[hi] becomes possible and genuinely ambiguous — you can no longer tell which side the seam is on without shrinking the window by one at a time (hi--) in that specific case, which degrades the worst case to O(n).

Q: Why is while (lo < hi) the right loop condition here, instead of the more familiar while (lo <= hi) from a standard “find a target value” binary search?

A standard binary search is hunting for a specific value and needs to check the case where the window has collapsed to one element before declaring failure — that’s what lo <= hi (with a separate check inside) is for.
This problem isn’t searching for a value — it’s narrowing a window down to a single index that is guaranteed to exist (the array always has a minimum). Once lo === hi, that index already IS the answer; there’s nothing left to decide, so the loop should stop rather than run one more comparison against itself.
Using lo <= hi here would let mid equal hi on the final iteration, comparing nums[hi] against itself — harmless, but wasted work, and a sign of not having thought through what the loop invariant actually guarantees.

Q: Trick question — what does this log?

const lo = 2 ** 31 - 2;       // 2147483646
const hi = 2 ** 31 - 1;       // 2147483647 (near Java/C++'s 32-bit int limit)
console.log(Math.floor((lo + hi) / 2));

function int32Add(a, b) { return (a + b) | 0; } // forces 32-bit signed wraparound
console.log(int32Add(lo, hi));

Answer: the first line logs 2147483646 — the correct midpoint. The second logs -3 — visibly wrong.
In Java or C++, lo and hi here would be right at the edge of a 32-bit signed int’s range (max 2147483647). Computing lo + hi the naive way genuinely overflows in those languages, wrapping around to a negative number — the classic reason binary search implementations there use lo + (hi - lo) / 2 instead of (lo + hi) / 2.
JS doesn’t have that failure mode for numbers in this range: all JS numbers are IEEE-754 doubles, which represent integers exactly up to Number.MAX_SAFE_INTEGER (9007199254740991, about 2^53) — nowhere near reached by adding two 32-bit-range values. The second console.log only goes wrong because | 0 deliberately forces 32-bit signed truncation (JS’s bitwise operators always do this) — that’s simulating the other languages’ bug on purpose, not something plain + and / would ever do on their own.
Practically: a JS array’s length is capped at 2^32 - 1 (4294967295) anyway, which is still comfortably under Number.MAX_SAFE_INTEGER — so Math.floor((lo + hi) / 2) is simply never at risk of overflow for any real array index in JS, and the lo + (hi - lo) / 2 defensive rewrite (needed in Java/C++) is not a thing you need to reach for here.

⚠ Trap: it’s tempting to port the “avoid overflow” idiom from Java/C++ binary search code into JS out of habit — it’s not wrong, exactly, just solving a problem JS numbers don’t actually have at realistic array sizes.

Quiz

1. Why does the binary search compare nums[mid] against nums[hi] rather than nums[lo]?

A) nums[mid] > nums[hi] reliably means mid is still in the unrotated high run, since a value can only exceed a later one across a wraparound — comparing against lo doesn’t give that guarantee
B) Comparing against hi is simply faster to compute than comparing against lo
C) It makes no real difference — comparing against either lo or hi gives the same guarantee

2. In the branch where nums[mid] <= nums[hi], why is hi = mid correct instead of hi = mid - 1?

A) mid could itself be the minimum in this branch, so discarding it with hi = mid - 1 can throw away the correct answer
B) hi = mid - 1 is correct too — it’s purely a style preference with no effect on the result
C) hi = mid - 1 only fails on arrays with an odd length

3. Why does this binary search use while (lo < hi) instead of the more familiar while (lo <= hi)?

A) The search narrows to a single guaranteed-to-exist index rather than hunting for a possibly-absent value — once lo === hi, that index is already the answer
B) lo <= hi would cause an infinite loop in every case
C) Both conditions behave identically here — it’s a stylistic choice

4. What is the actual complexity difference between the brute force and the optimal solution?

A) A real asymptotic win: O(n) linear scan versus O(log n) binary search, both O(1) space
B) Both are O(n) — the binary search only looks faster on small examples
C) They’re the same time complexity; the optimal solution only improves space usage

5. What happens when the array has been “rotated” 0 times, e.g. [11,13,15,17]?

A) It’s a valid, explicitly allowed input — both solutions handle it correctly with no special-casing, correctly returning nums[0] as the minimum
B) It’s an invalid input — a “rotated” array must always be rotated at least once
C) The binary search throws an error because there’s no rotation seam to find