Loading…

mediumBinary SearchLC #153Frequently asked

Find Minimum in Rotated Sorted Array

Q: How do you solve Find Minimum in Rotated Sorted Array using the Linear Scan (Baseline) approach?

When to use it: Name it as the O(n) bar — useful to confirm the answer, but the prompt wants O(log n). Track the smallest value seen while scanning once. **Why mention it.** A trivially correct reference and a complexity to beat. **Why it's wrong here.** The prompt demands `O(log n)`; the scan discards the fact that the array is two sorted runs with a single drop. Time complexity: O(n). Space complexity: O(1).

Q: How do you solve Find Minimum in Rotated Sorted Array using the Binary Search for the Pivot (Optimal) approach?

When to use it: The answer they want. Frame it as 'find the single drop point' and anchor the compare on nums[hi]. Maintain `[lo, hi]` and shrink it toward the pivot. **Why compare against `nums[hi]`.** The right end `nums[hi]` is a reliable reference for 'which side is the rotation on'. If `nums[mid] > nums[hi]`, then going from `mid` to `hi` we must pass through the drop — so the minimum lies strictly to the **right** of `mid`, and we set `lo = mid + 1` (mid itself can't be the minimum because something to its right is smaller). If instead `nums[mid] = nums[lo]` would wrongly push us right. **Why `hi = mid` and not `hi = mid - 1`.** When `nums[mid] <= nums[hi]`, mid is a *candidate* minimum, so excluding it could throw away the answer. Keeping it (`hi = mid`) is correct; progress is still guaranteed because the `lo = mid + 1` branch always shrinks, and in the `hi = mid` branch `mid < hi` whenever `lo < hi` (mid rounds down), so `hi` strictly decreases. **Why `while (lo < hi)`.** With `hi = mid`, a window of size 1 (`lo == hi`) already pinpoints the minimum, so we stop there and return `nums[lo]`. Using `lo <= hi` together with `hi = mid` would never let the window reach size 0 and would loop forever when `lo == hi == mid`. This `lo < hi` + `hi = mid` pairing is the standard 'find leftmost element satisfying a predicate' template. **Why no explicit equality check.** Elements are unique and we're not searching for a value, only the boundary, so there's no `nums[mid] == target` case — we converge purely by halving toward the drop. Time complexity: O(log n). Space complexity: O(1).

LCPractice

Binary Search · 3 of 16 · 9 min

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

In plain English

A rotation moves a suffix of the sorted array to the front, creating exactly one place where a bigger value is followed by a smaller one. That smaller value is the global minimum (the pivot). We binary search for it without ever needing the target.

Examples

Example 1

Input: nums = [3, 4, 5, 1, 2]
Output: 1
Note: Original [1,2,3,4,5] rotated 3 times; the minimum 1 sits at index 3.

Example 2

Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0
Note: Pivot is 0 at index 4.

Example 3

Input: nums = [11, 13, 15, 17]
Output: 11
Note: Effectively un-rotated; the minimum is the first element.

Constraints

n == nums.length
1 ≤ n ≤ 5000
-5000 ≤ nums[i] ≤ 5000
All the integers of nums are unique
nums is sorted and rotated between 1 and n times

Clarifying questions4First question: Are elements unique?Explore questions

Q1.Are elements unique?
Yes here. Duplicates (LeetCode 154) make nums[mid] == nums[hi] ambiguous and degrade the worst case to O(n).
Q2.Is the array guaranteed to be rotated at least once?
The statement says rotated between 1 and n times, and rotating n times returns the original — so a fully sorted array is a valid input and the code must handle it (it does: hi keeps moving left to index 0).
Q3.Should I compare mid to lo or to hi?
To hi. Comparing to lo can't distinguish a rotated from a non-rotated left segment; comparing to hi cleanly tells you which side the drop is on.
Q4.Return the value or the index?
The value here. If you needed the rotation count, you'd return the index lo instead.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

The minimum of a rotated sorted array is the unique 'pivot' — the only element smaller than its predecessor. Binary search by comparing nums[mid] to nums[hi]: if nums[mid] > nums[hi] the minimum is strictly to the right (lo = mid + 1); otherwise it's at mid or to its left (hi = mid). Loop while lo < hi and return nums[lo]. O(log n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can find a boundary (the rotation point) with binary search, choosing the right anchor to compare against and pairing `hi = mid` with `while (lo < hi)` correctly.

Where candidates slip

Comparing nums[mid] to nums[lo] (ambiguous on a non-rotated array), or writing `hi = mid - 1` with the `hi = mid` style and skipping the true minimum, or using `lo <= hi` and looping forever.

How to stand out

Explain that the minimum is the only element smaller than its neighbour, justify comparing to nums[hi], and note the loop invariant: the minimum is always inside [lo, hi].

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Linear Scan (Baseline)	`O(n)`	`O(1)`	Name it as the O(n) bar — useful to confirm the answer, but the prompt wants O(log n).	Read
2	Binary Search for the Pivot (Optimal)Optimal	`O(log n)`	`O(1)`	The answer they want. Frame it as 'find the single drop point' and anchor the compare on nums[hi].	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCompare nums[mid] with nums[hi]nums[mid] > nums[hi]?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Linear Scan (Baseline)

TimeO(n)SpaceO(1)

Name it as the O(n) bar — useful to confirm the answer, but the prompt wants O(log n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

With no cleverness, how do you find the smallest element of any array?

2Hint 2Explore hint

Track a running minimum across one pass.

3Hint 3Explore hint

O(n) — fine for correctness but ignores the sorted-rotated structure that allows O(log n).

A · Core idea

Track the smallest value seen while scanning once.

Why mention it. A trivially correct reference and a complexity to beat. Why it's wrong here. The prompt demands O(log n); the scan discards the fact that the array is two sorted runs with a single drop.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [3, 4, 5, 1, 2]

i=0..2

min = 3

State3,4,5 keep min=3

Final result1

C · Code with teaching comments

Reference implementation previewpublic int findMin(int[] nums) { int min = nums[0]; for (int num : nums) { if (num < min) { min = num;Explore the full code

solution.javaJava

Linear Scan (Baseline) — reference

2 teaching notes

1
public int findMin(int[] nums) {
2
    int min = nums[0];
3
    for (int num : nums) {
4
        // Running-minimum update; ignores structure → O(n).
5
        if (num < min) {
6
            min = num;
7
        }
8
    }
9
    // Smallest seen.
10
    return min;
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The minimum is special: it's the only element smaller than its left neighbour. A scan finds it the slow way; binary search finds that one discontinuity in log n.

ComplexityO(n) time, O(1) space — One pass, n comparisons, constant memory.

E · Edge cases and pitfalls2Submitting an O(n) scan when O(log n) is required.Explore edge cases

Pitfalls

Submitting an O(n) scan when O(log n) is required.
Initialising min to 0 instead of nums[0] — wrong for all-positive or all-negative arrays.

03.2

Approach 2 of 2 · Optimal

Binary Search for the Pivot (Optimal)

TimeO(log n)SpaceO(1)

The answer they want. Frame it as 'find the single drop point' and anchor the compare on nums[hi].

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The minimum is the only element smaller than the one before it. How can comparing the middle element to the LAST element tell you which side that drop is on?

2Hint 2Explore hint

If nums[mid] > nums[hi], the right portion is 'lower' and must contain the drop, so the minimum is to the right of mid.

3Hint 3Explore hint

Otherwise mid is part of the run that leads down to hi, so the minimum is mid or to its left — keep mid in the window with hi = mid, and loop while lo < hi.

A · Core idea

Maintain [lo, hi] and shrink it toward the pivot.

Why compare against `nums[hi]`. The right end nums[hi] is a reliable reference for 'which side is the rotation on'. If nums[mid] > nums[hi], then going from mid to hi we must pass through the drop — so the minimum lies strictly to the right of mid, and we set lo = mid + 1 (mid itself can't be the minimum because something to its right is smaller). If instead nums[mid] <= nums[hi], the segment [mid, hi] is already sorted (no drop), so the minimum is at mid or to its left; we set hi = mid, deliberately keeping mid because it might be the answer. Comparing to nums[lo] instead fails on an un-rotated array, where nums[mid] >= nums[lo] would wrongly push us right.

Why `hi = mid` and not `hi = mid - 1`. When nums[mid] <= nums[hi], mid is a candidate minimum, so excluding it could throw away the answer. Keeping it (hi = mid) is correct; progress is still guaranteed because the lo = mid + 1 branch always shrinks, and in the hi = mid branch mid < hi whenever lo < hi (mid rounds down), so hi strictly decreases.

Why `while (lo < hi)`. With hi = mid, a window of size 1 (lo == hi) already pinpoints the minimum, so we stop there and return nums[lo]. Using lo <= hi together with hi = mid would never let the window reach size 0 and would loop forever when lo == hi == mid. This lo < hi + hi = mid pairing is the standard 'find leftmost element satisfying a predicate' template.

Why no explicit equality check. Elements are unique and we're not searching for a value, only the boundary, so there's no nums[mid] == target case — we converge purely by halving toward the drop.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [4, 5, 6, 7, 0, 1, 2]

Array state

lo=0, hi=6

mid=3 (7) > hi(2) → go right

lo ↓

[0]

[1]

[2]

mid ↓

[3]

[4]

[5]

hi ↓

[6]

Current pointerResolved stateNot processed

Final result0

C · Code with teaching comments

solution.javaJava

Binary Search for the Pivot (Optimal) — optimal

6 teaching notes

1
public int findMin(int[] nums) {
2
    // Window covers the whole array; the minimum is always inside it.
3
    int lo = 0, hi = nums.length - 1;
4
    // Strict `<` because the hi = mid branch keeps the window non-empty; lo == hi is
5
    // the answer.
6
    while (lo < hi) {
7
        int mid = lo + (hi - lo) / 2;
8
        // Going mid→hi crosses the drop, so the min is strictly right of mid.
9
        if (nums[mid] > nums[hi]) {
10
            // Exclude mid — it can't be the minimum here.
11
            lo = mid + 1;
12
        } else {
13
            // [mid, hi] is sorted; mid might BE the min, so keep it.
14
            hi = mid;
15
        }
16
    }
17
    // lo == hi now points exactly at the pivot.
18
    return nums[lo];
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

This is the boundary-finding form of binary search: we're locating the leftmost index whose value is <= nums[hi], i.e. the start of the lower sorted run. Recognising 'find the first index where a monotone predicate flips' lets you reuse this exact lo < hi / hi = mid skeleton for Search Insert Position, Find Peak Element, and rotation-count problems.

ComplexityO(log n) time, O(1) space — Each iteration discards half the window with O(1) work → O(log n) iterations, O(1) space.

E · Edge cases and pitfalls8nums = [1] — lo == hi from the start → loop body never runs → return nums[0] = 1.Explore edge cases

Edge cases handled

nums = [1]lo == hi from the start → loop body never runs → return nums[0] = 1.
nums = [2, 1]mid=0 (2) > hi(1) → lo=1; lo==hi → return nums[1]=1.
nums = [1, 2, 3]Un-rotated: every mid <= hi → hi keeps moving to 0 → return nums[0]=1.
nums = [3, 1, 2]mid=1 (1) <= hi(2) → hi=1; then lo=0,hi=1,mid=0 (3) > hi(1) → lo=1 → return 1.

Pitfalls

Comparing nums[mid] to nums[lo] — fails on un-rotated arrays.
Writing hi = mid - 1 with this template — skips the actual minimum.
Using `while (lo <= hi)` with hi = mid — infinite loop when lo == hi == mid.
Returning nums[mid] inside the loop instead of nums[lo] after convergence.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int findMin(int[] nums) { int lo = 0, hi = nums.length - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] > nums[hi]) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Comparing to nums[lo] instead of nums[hi]

On a non-rotated array nums[mid] >= nums[lo] is always true, so anchoring on lo wrongly pushes the search right and never finds the front-most minimum.

Explore the code comparison

Don't write this

if nums[mid] >= nums[lo]:
    lo = mid + 1
else:
    hi = mid

Write this instead

if nums[mid] > nums[hi]:
    lo = mid + 1
else:
    hi = mid

hi = mid - 1 drops the minimum

When nums[mid] <= nums[hi], mid is itself a candidate for the minimum. Setting hi = mid - 1 can step over it and return the wrong element.

Explore the code comparison

Don't write this

if (nums[mid] > nums[hi]) {
    lo = mid + 1;
} else {
    hi = mid - 1;   // skips a possible min at mid
}

Write this instead

if (nums[mid] > nums[hi]) {
    lo = mid + 1;
} else {
    hi = mid;       // keep mid as a candidate
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search for the pivot via mid-vs-hi

Code pattern to memorize

lo, hi = 0, n - 1
while lo < hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] > nums[hi]: lo = mid + 1
    else: hi = mid
return nums[lo]

Rules to remember

1Compare nums[mid] to nums[hi], not nums[lo] — comparing to lo is ambiguous when the array isn't rotated.
2nums[mid] > nums[hi] ⇒ the drop is to the right ⇒ lo = mid + 1 (mid can't be the min).
3Else ⇒ mid could be the min, so hi = mid (keep mid in the window — do not write mid - 1).
4Loop condition is while (lo < hi) because hi = mid keeps the window non-empty; with <= plus hi = mid you'd loop forever.
5When the loop ends lo == hi points at the minimum — return nums[lo].

Use this pattern when

Find the smallest element / rotation count / pivot of a rotated sorted array in O(log n)
Locate the single discontinuity in an otherwise-sorted sequence
As a sub-routine before searching a rotated array by splitting it at the pivot

Choose another pattern when

Array isn't rotated and you just want min of arbitrary data → linear scan is O(n) and unavoidable
Duplicates allowed (LeetCode 154) → nums[mid] == nums[hi] is ambiguous; shrink hi by one, worst case O(n)
You also need to *search* for a target → combine with Search in Rotated Sorted Array

Interview takeaway

Comparing the midpoint to the right end (not the left) is the clean way to detect which side the rotation 'drop' is on. The `hi = mid` (not `mid - 1`) move with a `lo < hi` loop is the canonical boundary-finding template — memorise the pairing.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBoundary-finding binary search (find the single rotation drop). Recognise it when you must locate the one discontinuity in an otherwise-sorted array. The `while (lo < hi)` + `hi = mid` template is shared with Find Peak Element and Search Insert Position.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Find Minimum in Rotated Sorted Array II
Coming soon
Duplicates allowed — on nums[mid] == nums[hi], do hi -= 1; worst case O(n).
Search in Rotated Sorted Array
Use the pivot idea, then binary search the correct half for a target.
Find Peak Element
Same boundary-finding template: compare mid to a neighbour and move toward the higher side.
Binary Search
The base template this specialises — inclusive bounds and overflow-safe mid.

Same pattern

←

Search in Rotated Sorted Array

Continue · Next problem

Search a 2D Matrix

mediumBinary SearchLC #153Frequently asked

Find Minimum in Rotated Sorted Array

LCPractice

Binary Search · 3 of 16 · 9 min

You must write an algorithm that runs in O(log n) time.

In plain English

Examples

Example 1

Input: nums = [3, 4, 5, 1, 2]
Output: 1
Note: Original [1,2,3,4,5] rotated 3 times; the minimum 1 sits at index 3.

Example 2

Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0
Note: Pivot is 0 at index 4.

Example 3

Input: nums = [11, 13, 15, 17]
Output: 11
Note: Effectively un-rotated; the minimum is the first element.

Constraints

n == nums.length
1 ≤ n ≤ 5000
-5000 ≤ nums[i] ≤ 5000
All the integers of nums are unique
nums is sorted and rotated between 1 and n times

Clarifying questions4First question: Are elements unique?Explore questions

Q1.Are elements unique?
Yes here. Duplicates (LeetCode 154) make nums[mid] == nums[hi] ambiguous and degrade the worst case to O(n).
Q2.Is the array guaranteed to be rotated at least once?
The statement says rotated between 1 and n times, and rotating n times returns the original — so a fully sorted array is a valid input and the code must handle it (it does: hi keeps moving left to index 0).
Q3.Should I compare mid to lo or to hi?
To hi. Comparing to lo can't distinguish a rotated from a non-rotated left segment; comparing to hi cleanly tells you which side the drop is on.
Q4.Return the value or the index?
The value here. If you needed the rotation count, you'd return the index lo instead.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can find a boundary (the rotation point) with binary search, choosing the right anchor to compare against and pairing `hi = mid` with `while (lo < hi)` correctly.

Where candidates slip

Comparing nums[mid] to nums[lo] (ambiguous on a non-rotated array), or writing `hi = mid - 1` with the `hi = mid` style and skipping the true minimum, or using `lo <= hi` and looping forever.

How to stand out

Explain that the minimum is the only element smaller than its neighbour, justify comparing to nums[hi], and note the loop invariant: the minimum is always inside [lo, hi].

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Linear Scan (Baseline)	`O(n)`	`O(1)`	Name it as the O(n) bar — useful to confirm the answer, but the prompt wants O(log n).	Read
2	Binary Search for the Pivot (Optimal)Optimal	`O(log n)`	`O(1)`	The answer they want. Frame it as 'find the single drop point' and anchor the compare on nums[hi].	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Linear Scan (Baseline)

TimeO(n)SpaceO(1)

Name it as the O(n) bar — useful to confirm the answer, but the prompt wants O(log n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

With no cleverness, how do you find the smallest element of any array?

2Hint 2Explore hint

Track a running minimum across one pass.

3Hint 3Explore hint

O(n) — fine for correctness but ignores the sorted-rotated structure that allows O(log n).

A · Core idea

Track the smallest value seen while scanning once.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [3, 4, 5, 1, 2]

i=0..2

min = 3

State3,4,5 keep min=3

Final result1

C · Code with teaching comments

Reference implementation previewpublic int findMin(int[] nums) { int min = nums[0]; for (int num : nums) { if (num < min) { min = num;Explore the full code

solution.javaJava

Linear Scan (Baseline) — reference

2 teaching notes

1
public int findMin(int[] nums) {
2
    int min = nums[0];
3
    for (int num : nums) {
4
        // Running-minimum update; ignores structure → O(n).
5
        if (num < min) {
6
            min = num;
7
        }
8
    }
9
    // Smallest seen.
10
    return min;
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The minimum is special: it's the only element smaller than its left neighbour. A scan finds it the slow way; binary search finds that one discontinuity in log n.

ComplexityO(n) time, O(1) space — One pass, n comparisons, constant memory.

E · Edge cases and pitfalls2Submitting an O(n) scan when O(log n) is required.Explore edge cases

Pitfalls

Submitting an O(n) scan when O(log n) is required.
Initialising min to 0 instead of nums[0] — wrong for all-positive or all-negative arrays.

03.2

Approach 2 of 2 · Optimal

Binary Search for the Pivot (Optimal)

TimeO(log n)SpaceO(1)

The answer they want. Frame it as 'find the single drop point' and anchor the compare on nums[hi].

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The minimum is the only element smaller than the one before it. How can comparing the middle element to the LAST element tell you which side that drop is on?

2Hint 2Explore hint

If nums[mid] > nums[hi], the right portion is 'lower' and must contain the drop, so the minimum is to the right of mid.

3Hint 3Explore hint

Otherwise mid is part of the run that leads down to hi, so the minimum is mid or to its left — keep mid in the window with hi = mid, and loop while lo < hi.

A · Core idea

Maintain [lo, hi] and shrink it toward the pivot.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [4, 5, 6, 7, 0, 1, 2]

Array state

lo=0, hi=6

mid=3 (7) > hi(2) → go right

lo ↓

[0]

[1]

[2]

mid ↓

[3]

[4]

[5]

hi ↓

[6]

Current pointerResolved stateNot processed

Final result0

C · Code with teaching comments

solution.javaJava

Binary Search for the Pivot (Optimal) — optimal

6 teaching notes

1
public int findMin(int[] nums) {
2
    // Window covers the whole array; the minimum is always inside it.
3
    int lo = 0, hi = nums.length - 1;
4
    // Strict `<` because the hi = mid branch keeps the window non-empty; lo == hi is
5
    // the answer.
6
    while (lo < hi) {
7
        int mid = lo + (hi - lo) / 2;
8
        // Going mid→hi crosses the drop, so the min is strictly right of mid.
9
        if (nums[mid] > nums[hi]) {
10
            // Exclude mid — it can't be the minimum here.
11
            lo = mid + 1;
12
        } else {
13
            // [mid, hi] is sorted; mid might BE the min, so keep it.
14
            hi = mid;
15
        }
16
    }
17
    // lo == hi now points exactly at the pivot.
18
    return nums[lo];
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(log n) time, O(1) space — Each iteration discards half the window with O(1) work → O(log n) iterations, O(1) space.

E · Edge cases and pitfalls8nums = [1] — lo == hi from the start → loop body never runs → return nums[0] = 1.Explore edge cases

Edge cases handled

nums = [1]lo == hi from the start → loop body never runs → return nums[0] = 1.
nums = [2, 1]mid=0 (2) > hi(1) → lo=1; lo==hi → return nums[1]=1.
nums = [1, 2, 3]Un-rotated: every mid <= hi → hi keeps moving to 0 → return nums[0]=1.
nums = [3, 1, 2]mid=1 (1) <= hi(2) → hi=1; then lo=0,hi=1,mid=0 (3) > hi(1) → lo=1 → return 1.

Pitfalls

Comparing nums[mid] to nums[lo] — fails on un-rotated arrays.
Writing hi = mid - 1 with this template — skips the actual minimum.
Using `while (lo <= hi)` with hi = mid — infinite loop when lo == hi == mid.
Returning nums[mid] inside the loop instead of nums[lo] after convergence.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int findMin(int[] nums) { int lo = 0, hi = nums.length - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] > nums[hi]) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Comparing to nums[lo] instead of nums[hi]

On a non-rotated array nums[mid] >= nums[lo] is always true, so anchoring on lo wrongly pushes the search right and never finds the front-most minimum.

Explore the code comparison

Don't write this

if nums[mid] >= nums[lo]:
    lo = mid + 1
else:
    hi = mid

Write this instead

if nums[mid] > nums[hi]:
    lo = mid + 1
else:
    hi = mid

hi = mid - 1 drops the minimum

When nums[mid] <= nums[hi], mid is itself a candidate for the minimum. Setting hi = mid - 1 can step over it and return the wrong element.

Explore the code comparison

Don't write this

if (nums[mid] > nums[hi]) {
    lo = mid + 1;
} else {
    hi = mid - 1;   // skips a possible min at mid
}

Write this instead

if (nums[mid] > nums[hi]) {
    lo = mid + 1;
} else {
    hi = mid;       // keep mid as a candidate
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search for the pivot via mid-vs-hi

Code pattern to memorize

lo, hi = 0, n - 1
while lo < hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] > nums[hi]: lo = mid + 1
    else: hi = mid
return nums[lo]

Rules to remember

1Compare nums[mid] to nums[hi], not nums[lo] — comparing to lo is ambiguous when the array isn't rotated.
2nums[mid] > nums[hi] ⇒ the drop is to the right ⇒ lo = mid + 1 (mid can't be the min).
3Else ⇒ mid could be the min, so hi = mid (keep mid in the window — do not write mid - 1).
4Loop condition is while (lo < hi) because hi = mid keeps the window non-empty; with <= plus hi = mid you'd loop forever.
5When the loop ends lo == hi points at the minimum — return nums[lo].

Use this pattern when

Find the smallest element / rotation count / pivot of a rotated sorted array in O(log n)
Locate the single discontinuity in an otherwise-sorted sequence
As a sub-routine before searching a rotated array by splitting it at the pivot

Choose another pattern when

Array isn't rotated and you just want min of arbitrary data → linear scan is O(n) and unavoidable
Duplicates allowed (LeetCode 154) → nums[mid] == nums[hi] is ambiguous; shrink hi by one, worst case O(n)
You also need to *search* for a target → combine with Search in Rotated Sorted Array

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Find Minimum in Rotated Sorted Array II
Coming soon
Duplicates allowed — on nums[mid] == nums[hi], do hi -= 1; worst case O(n).
Search in Rotated Sorted Array
Use the pivot idea, then binary search the correct half for a target.
Find Peak Element
Same boundary-finding template: compare mid to a neighbour and move toward the higher side.
Binary Search
The base template this specialises — inclusive bounds and overflow-safe mid.

Same pattern

←

Search in Rotated Sorted Array

Continue · Next problem

Search a 2D Matrix