LeetCode 153 ·
Medium
Find Minimum in Rotated Sorted Array
Find the minimum in an ascending array rotated an unknown number of times.
Try it
Step through the core mechanic. The simulator below runs the binary search shape this problem is built on.
Interactive · Binary search walkthrough Sorted array; halve the search range at each step.
0
-7
L
1
-3
2
0
3
2
4
5
5
8
6
11
7
14
8
17
9
21
10
25
11
30
H
start: lo=0, hi=11, mid=5, a[mid]=8
range12 log₂(n)≤ 4 step0 / 3
Why binary search is O(log n).
Each step halves the search range. Starting from
n, after
k steps the range is n / 2ᵏ; the search ends when
this drops below 1, so k ≤ log₂(n). For n = 10⁹,
that's ≤ 30 steps. The interview corollary: if the constraint is
n ≤ 10⁹, you need an O(log n) approach — binary search is
usually the one.The approach
Compare mid to the right end. If nums[mid] > nums[hi] the minimum is to the right of mid; otherwise it is mid or to its left. Converge on the rotation point.
| Aspect | Value |
|---|---|
| Pattern | Binary search |
| Recognise it by | Sorted then rotated; find the pivot. |
| Time complexity | O(log n) |
| Space complexity | O(1) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.