Find Minimum in Rotated Sorted Array
Problem
n), so it may look like [4,5,6,7,0,1,2].
Given the rotated array nums, return its smallest element in
O(log n) time.nums = [3,4,5,1,2]Output1nums = [4,5,6,7,0,1,2]Output0nums = [11,13,15,17]Output11 (rotated n times = unchanged)1 ≤ n ≤ 5000 · -5000 ≤ nums[i] ≤ 5000 · all values distinct · O(log n) required
Try it yourself
class Solution {
public int findMin(int[] nums) {
}
}
nums[mid] with the last element of the window. If it
is bigger, the “drop” (and so the minimum) is strictly to the right of mid;
otherwise mid..hi is sorted and the minimum is at mid or to its left.Instinct Sorted data, a rotated array, or find the min/max X that works where a yes/no test flips only once - halve the search space every step.
Memory hack Find the fence - every candidate reads NO NO NO YES YES, and binary search just walks to where the fence stands.
Open the Binary Search guide →Approaches
Brute ForceLinear Scan
O(n)Space O(1)The minimum of any array can be found by looking at every element once and keeping the smallest. This never uses the fact that the array is two sorted runs glued together.
public int findMin(int[] nums) { int min = nums[0]; for (int x : nums) min = Math.min(min, x); return min; }
Trivially correct, but O(n) breaks the logarithmic requirement.
OptimalBinary Search Against the Right End
O(log n)Space O(1)A rotated array is a high run followed by a low run; every value in the high
run is larger than every value in the low run, including nums[hi]. So
nums[mid] > nums[hi] means mid sits in the high run and the minimum is
after it; otherwise mid is in the low run and the minimum is mid or earlier. The
window shrinks until a single element — the minimum — is left.
public 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]) lo = mid + 1; // drop is to the right of mid else hi = mid; // mid..hi sorted: min is mid or left } return nums[lo]; }
Dry runnums = [3,4,5,1,2]
- lo=0 hi=64lo567m012hi7 > 2 → lo=4
- lo=4 hi=645670lo1m2hi1 ≤ 2 → hi=5
- lo=4 hi=545670lo m1hi20 ≤ 1 → hi=4
- lo=hi=445670lo hi12min = 0 ✔
Halves the search space each step and handles the unrotated case with no special code.
nums[hi], not nums[lo]: the left end cannot
tell “unrotated” apart from “minimum is to the right”.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Linear Scan | O(n) | O(1) |
| Optimal | Binary Search Against the Right End | O(log n) | O(1) |
- Comparing
nums[mid]withnums[0]and mishandling an unrotated array. - Using
hi = mid - 1when mid itself might be the minimum. - Looping with
lo <= hiandhi = mid— never terminates.
- Draw the array as two ascending ramps with a cliff, then place mid on the picture.
- Explain why every high-run value exceeds
nums[hi]— that justifies each move. - Mention the duplicates follow-up (LC 154): when equal, shrink
hiby one.