153. Find Minimum in Rotated Sorted Array

153

MediumBinary SearchBinary search comparing mid to the right boundaryBinary search for the rotation point

Find Minimum in Rotated Sorted Array

Given a sorted array of unique integers that has been rotated between 1 and n times, return the minimum element. You must run in O(log n) time.

Open official problem prompt ↗

In plain English

Find the pivot where the ascending order wraps around, which holds the smallest value, without scanning every element.

Picture it like this

Like flipping through a Rolodex that someone rotated mid-way: you keep splitting the deck and asking 'did the alphabet reset in this chunk?' to home in on the single reset point.

Example

Input: nums = [3, 4, 5, 1, 2]
Output: 1
Why: The array was rotated so that the smallest value 1 now sits at index 3.

Constraints

n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000All integers of nums are uniquenums is sorted and rotated between 1 and n times

Pattern lesson

See the pattern, then code

Binary search for the rotation point

↗

Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. The minimum is the only element smaller than its predecessor; comparing nums[mid] to nums[hi] tells you which side the unsorted drop (and therefore the minimum) lives on.

New words, made simpleKnow these before the algorithm

Inflection point: The index of the minimum, the one place where a larger value is immediately followed by a smaller one.
Right anchor: Comparing against nums[hi] rather than nums[lo], which reliably distinguishes the sorted from unsorted side.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Linear scan for the min

Ignores the sorted structure and misses the log-time requirement.

Track the running minimum across all elements.

Time O(n)Space O(1)

Best choiceBinary search vs nums[hi]

Clean, correct, and optimal.

Compare mid to the right boundary to decide which half holds the drop.

Time O(log n)Space O(1)

The rule we keep true

Invariant

The minimum element always lies within the closed window [lo, hi].

Why this is correct

Reasoning

If nums[mid] > nums[hi], the drop must be to the right of mid, so mid cannot be the minimum and lo advances past it. If nums[mid] <= nums[hi], the right segment is sorted, so the minimum is mid or left of it, and hi collapses to mid. The window shrinks each step until lo equals hi at the minimum.

The algorithm in three movesSay these aloud before coding

1Set lo and hi to the array ends

lo=0, hi=4, mid=2 -> nums[2]=5 > nums[4]=2, lo=3

2While lo < hi, compute mid

lo=3, hi=4, mid=3 -> nums[3]=1 <= nums[4]=2, hi=3

3If nums[mid] > nums[hi], the minimum is strictly right of mid, so lo = mid + 1

lo==hi==3 -> return nums[3]=1

4Otherwise the minimum is at mid or left, so hi = mid

5Return nums[lo] when the window collapses

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readlo=0, hi=4

2 · AskIs nums[2]=5 greater than nums[4]=2?

3 · Update statedrop is on the right

4 · Resultyes, lo becomes 3

Key takeaway

The window narrows toward index 3, where the minimum value 1 sits.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 4Half-open loop
Using lo < hi (not <=) means the loop ends exactly when the window pins a single candidate.
2
Lines 6-7Discard the sorted left
nums[mid] > nums[hi] proves the minimum is strictly right, so mid is excluded via lo = mid + 1.
3
Lines 8-9Keep mid as candidate
Otherwise mid could itself be the minimum, so hi = mid keeps it in the window.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Array of length 1
Array rotated n times so it looks fully sorted (minimum at index 0)
Two-element arrays like [2,1] and [1,2]

Common beginner mistakes

Comparing nums[mid] to nums[lo] instead of nums[hi], which fails when the array is already sorted
Writing hi = mid - 1 and accidentally skipping the true minimum
Using lo <= hi with hi = mid, causing an infinite loop

Check your understanding

Why compare nums[mid] to nums[hi] and not nums[lo]?

Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Binary Search