codebrew.ai
Medium
Binary Search

Find Minimum in Rotated Sorted Array

The minimum is the only element smaller than its predecessor — binary search the rotation point.

Approach

Compare nums[mid] to nums[hi]. If nums[mid] > nums[hi], the pivot (minimum) is to the right, so move lo up; otherwise it's at mid or to the left, so move hi down. Converge until lo == hi, which is the minimum.

Time complexity

O(log n)

Space complexity

O(1)

Common mistake

Comparing to nums[lo] instead of nums[hi] — the comparison to the right boundary is what stays correct under rotation.

Interactive walkthrough — step through it below, free and without an account

Problem

You are given an ascending array of distinct integers that may have been rotated around an unknown position. Return the smallest value in the array while using a logarithmic-time strategy. The array may also be unrotated, in which case its first element is the minimum.

Examples

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

Output: 0

The sorted array was rotated at 0, and 0 is the only element smaller than the value immediately before it.

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

Output: 1

The rotation point is between 5 and 1, so the minimum is 1.

Problem

Problem

You are given an ascending array of distinct integers that may have been rotated around an unknown position. Return the smallest value in the array while using a logarithmic-time strategy. The array may also be unrotated, in which case its first element is the minimum.

Problem and Goal

Learning goal: Recognize why the minimum in a rotated sorted array can be found without checking every element.

Core idea A sorted array has no downward step: every value is at least as large as the one before it. Rotation creates exactly one such break, where the minimum follows the maximum. Finding that break is equivalent to finding the minimum.

The input contains distinct values, so the minimum is unambiguous. Our goal is to locate its index in O(log n) time and return the value at that index.

Algorithm plan

  • Keep a search interval from lo through hi.
  • Inspect mid, the middle index.
  • Compare nums[mid] with nums[hi] to decide which half contains the rotation point.
  • Stop when lo == hi.

Micro-example For [4,5,6,7,0,1,2], the downward break is 7 → 0. The answer is therefore the value at the rotation point: 0.

Pitfalls

  • Do not linearly scan for the downward step; that loses the logarithmic bound.
  • The array can be rotated zero times, so the first element may already be the minimum.
  • Use nums[hi] as the comparison boundary, not nums[lo].

Recap

  • Rotation creates one pivot where the minimum begins.
  • Binary search can isolate that pivot.
  • The final index lo == hi stores the minimum.

Problem and Goal

The rotation point is the minimum

In [4, 5, 6, 7, 0, 1, 2], the only downward transition is 7 → 0. That successor, 0, is the minimum.

Search for the pivot instead of scanning every value.

Key Idea: Compare with the Right Boundary

Learning goal: Understand why comparing nums[mid] with nums[hi] identifies the correct half.

Core idea The right boundary tells us which sorted section contains mid. If nums[mid] > nums[hi], then mid lies in the left, larger section of the rotation. The minimum must be strictly to the right of mid, so we can set lo = mid + 1.

Otherwise, nums[mid] <= nums[hi]. The suffix from mid to hi is ordered, which means the pivot is at mid or somewhere to its left. We preserve mid by setting hi = mid.

Algorithm plan

  • Initialize lo = 0 and hi = n - 1.
  • Compute mid = lo + (hi - lo) // 2.
  • If nums[mid] > nums[hi], discard lo..mid and move lo to mid + 1.
  • Otherwise, keep mid and move hi to mid.
  • Return nums[lo] when the interval collapses.

Micro-example With mid = 3, nums[mid] = 7, and nums[hi] = 2, 7 > 2. Therefore the pivot is right of index 3, so lo becomes 4.

Pitfalls

  • When nums[mid] <= nums[hi], do not use hi = mid - 1; mid may be the answer.
  • The comparison is directional: > means move right, otherwise move left or stay.
  • Distinct values make equality safe in the second branch.

Recap

  • nums[mid] > nums[hi] means the pivot is right of mid.
  • Otherwise, the pivot is at mid or left of it.
  • Comparing with the right boundary keeps this reasoning valid under rotation.

Key Idea: Compare with the Right Boundary

If nums[mid] > nums[hi], the middle is in the larger left section, so the minimum lies strictly to the right.

7 > 2 ⇒ lo = mid + 1

Main Approach and Correctness

Learning goal: Turn the comparison rule into a safe binary-search invariant.

Core idea Maintain the invariant that the minimum is always inside the closed interval [lo, hi]. Each comparison discards a region that cannot contain the pivot, while the branch hi = mid deliberately retains mid because it may be the minimum.

The search never needs to identify the predecessor explicitly. Instead, the relative order between nums[mid] and the rightmost value reveals whether the interval crosses the rotation point.

Algorithm plan

  • Start with the whole array as the candidate interval.
  • Repeatedly choose mid.
  • If nums[mid] > nums[hi], set lo = mid + 1.
  • Otherwise set hi = mid.
  • When one index remains, return nums[lo].
python
while lo < hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] > nums[hi]:
        lo = mid + 1
    else:
        hi = mid
return nums[lo]

Micro-example The interval [0, 6] becomes [4, 6], then [4, 5], then [4, 4]. The invariant guarantees that index 4 still contains the pivot throughout.

Pitfalls

  • Use while lo < hi, so the final one-element interval is not discarded.
  • Use mid + 1 only in the > branch, where mid is proven not to be the minimum.
  • Keep the interval closed; both endpoints are candidates.

Recap

  • The invariant is “the minimum lies in [lo, hi].”
  • Every iteration removes at least half the remaining candidates.
  • Retaining mid in the second branch ensures correctness.

Main Approach and Correctness

ApproachTimeSpaceCore decision
Binary searchO(log n)O(1)Compare nums[mid] with nums[hi]
Linear scanO(n)O(1)Check each value for the minimum

Walkthrough: Locate 0 Step by Step

Learning goal: Trace every interval update on the example [4,5,6,7,0,1,2].

Core idea We begin with every index as a candidate. At each step, nums[hi] acts as the reference value for the right sorted portion. A middle value larger than that reference proves that the rotation point is farther right; a middle value no larger than it lets us keep the middle and search left.

The important distinction is whether mid can still be the answer. In the > case it cannot, so we move past it. In the other case it can, so hi moves onto mid rather than before it.

Algorithm plan

  • Check indices 0 through 6.
  • Compare index 3 with index 6: 7 > 2, so search indices 4 through 6.
  • Compare index 5 with index 6: 1 <= 2, so search indices 4 through 5.
  • Compare index 4 with index 5: 0 <= 1, so search index 4.
  • Return nums[4] = 0.

Micro-example The intervals shrink as [0,6] → [4,6] → [4,5] → [4,4]. The final candidate is index 4, where the minimum value is 0.

Pitfalls

  • A sorted-looking right half does not mean the minimum is at hi; it may be at mid or left.
  • Record the updated interval after each comparison, not before it.
  • The answer is a value, while the binary search primarily tracks an index.

Recap

  • Each decision preserves index 4 as a candidate.
  • The interval reaches one index after three comparisons.
  • The traced result is 0.

Walkthrough: Locate 0 Step by Step

Animates the exact binary-search trace for the lesson's first example.

Binary search
1 / 7
Inspect index 3: 7 is larger than the right boundary value 2.

Array

4567mid012
lo=0hi=6mid=3target=minimumcheck: mid=7 > target

Action: inspect middle

A larger middle value means the pivot is to the right.The minimum remains inside indices 0 through 6.
1 / 7

Pitfalls and Edge Cases

Learning goal: Avoid the boundary mistake that makes this binary search unreliable.

Core idea The right boundary is special because it lets us determine whether mid belongs to the rotated, larger section or the sorted suffix. Comparing with nums[lo] does not provide the same stable signal: the left endpoint may itself be in either section, and its relationship with mid can be ambiguous after rotation.

The algorithm also handles unrotated arrays. If the array is [1,2,3,4], every middle value is less than the right boundary, so hi moves left until index 0 remains.

Algorithm plan

  • Compare only nums[mid] and nums[hi].
  • For nums[mid] > nums[hi], use lo = mid + 1.
  • Otherwise, use hi = mid.
  • Test one-element and unrotated arrays explicitly.

Micro-example For [1,2,3,4], 3 <= 4, then 2 <= 3, then 1 <= 2. The interval converges at index 0, returning 1.

Pitfalls

  • Do not compare to nums[lo] instead of nums[hi]. The right-boundary comparison stays correct under rotation.
  • Do not decrement hi in the second branch; mid may hold the minimum.
  • Do not assume the minimum is always near the middle or at an endpoint.

Recap

  • The right boundary is the reliable reference.
  • hi = mid preserves a possible answer.
  • Zero rotation and one-element arrays require no special code.

Pitfalls and Edge Cases

For a rotated sorted array, which rule is correct?

Complexity and Wrap-up

Learning goal: Connect interval halving to the target complexity and implement the final solution confidently.

Core idea Each iteration removes a portion of the candidate interval while preserving the minimum. Since the interval is repeatedly reduced by about half, the number of comparisons grows logarithmically with n. The algorithm stores only a few indices, so its auxiliary memory remains constant.

The returned value is nums[lo] after convergence. No separate pivot search, sorting step, or predecessor check is necessary.

Algorithm plan

  • Set lo = 0 and hi = n - 1.
  • While lo < hi, calculate mid.
  • Compare nums[mid] to nums[hi] and keep the valid half.
  • Return nums[lo].

Micro-example For seven values, the candidate counts go from 7 to 3 to 2 to 1. That shrinking pattern is the signature of O(log n) time.

Pitfalls

  • Do not sort the input: sorting costs O(n log n) and discards the rotation structure.
  • Do not allocate a second array; it is unnecessary.
  • Remember that lo is an index during the search and nums[lo] is the final answer.

Recap

  • Time complexity: O(log n).
  • Extra space: O(1).
  • The converged boundary is the rotation point and minimum.

Complexity and Wrap-up

Shows the logarithmic search cost and constant auxiliary space.

Complexity analysis
Time
O(log n)
Space
O(1)
Where the time goes
  • Binary-search iterationsThe candidate interval is halved each iteration.dominantO(log n)
  • Boundary comparisonEach iteration performs one constant-time comparison.O(1)
  • Index storageOnly lo, hi, and mid are stored.O(1)
How it grows
input size n →opsO(n²)O(n log n)O(n)O(log n)O(1)
Roughly what that costs
n101001,00010,000
O(log n)371013
O(n)101001K10K

Binary search finds the rotation point in logarithmic time while using constant extra space.

Now try it on your own problem

Paste any LeetCode problem — or one of your own — and codebrew builds a walkthrough like this one for it.

Build a lesson from any problem

Related problems

Search in Rotated Sorted Array
Medium
Binary Search
Easy