LeetCode 33 ·
Medium
Search in Rotated Sorted Array
Search a target in an ascending array rotated at an unknown pivot.
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
At each step one half is sorted. Detect which half is sorted by comparing endpoints, test whether the target lies inside that sorted half, and recurse into the correct side.
| Aspect | Value |
|---|---|
| Pattern | Binary search |
| Recognise it by | Find a value in a rotated sorted array in O(log n). |
| 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.