Search in Rotated Sorted Array
On this page
Problem statement
A sorted array of distinct integers has been rotated at some unknown position (for example [0, 1, 2, 4, 5, 6, 7] became [4, 5, 6, 7, 0, 1, 2]). Given the rotated array and a target, return the target's index, or −1 if it isn't there, in O(log n) time.
The O(log n) requirement rules out a scan. The trick is that even a rotated array still has a sorted half on one side of any midpoint, and that's enough to keep binary search working. Original problem: LeetCode 33.
Example

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
Constraints (assumed)
- 1 ≤ n ≤ 5,000 (the method works for any n).
- All values distinct; −10⁴ ≤ value ≤ 10⁴.
What this question tests
- Adapting binary search to an array that is only piecewise sorted.
- Finding an invariant that holds at every step (one half is sorted).
- Getting the boundary conditions (
≤vs<) right.
Questions to ask first
- Are values distinct? (Here: yes. With duplicates, the worst case becomes O(n); see Variants.)
- Could the array not be rotated at all? (Yes; the same code handles it.)
- Return any index or the first? With distinct values there's only one.
- Is O(n) acceptable? (No; the point is O(log n).)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.