Find a target in a rotated sorted array in O(log n) by deciding which half is sorted at each step of binary search. A top Google/Meta question.
The problem
nums was sorted ascending (distinct values) and then rotated at an unknown pivot, e.g. [4, 5, 6, 7, 0, 1, 2]. Return the index of target, or -1. Must be O(log n).
Examples
Example 1
Input
search_rotated([4, 5, 6, 7, 0, 1, 2], 0)
Expected output
4
Example 2
Input
search_rotated([4, 5, 6, 7, 0, 1, 2], 3)
Expected output
-1
+ 5 hidden tests on Submit — not rotated.
Edge cases to ask about
- Not rotated
- One or two elements
- Target at the pivot
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.
Pick both to reveal the answer.
Measure it
Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| Linear scan | O(n) | O(1) | |
| Find the pivot, then binary search | O(log n) | O(1) | Two passes. |
| bestOne binary search: one half is always sorted | O(log n) | O(1) |
Walkthrough of the optimal approach (try it yourself first)
At any mid, one half is sorted. If nums[lo] <= nums[mid], the left half is sorted. Then the target is in it exactly when nums[lo] <= target < nums[mid]; otherwise search the right. The mirror logic applies when the right half is sorted.
The <= in nums[lo] <= nums[mid] matters when lo == mid (two elements left).
Complexity: O(log n) time, O(1) space. Each step discards half of the range.
Reveal the reference solution
def search_rotated(nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = (lo + hi) // 2 if nums[mid] == target: return mid if nums[lo] <= nums[mid]: # left half is sorted if nums[lo] <= target < nums[mid]: hi = mid - 1 else: lo = mid + 1 else: # right half is sorted if nums[mid] < target <= nums[hi]: lo = mid + 1 else: hi = mid - 1 return -1
The brute force, for comparison
def search_rotated(nums, target): return nums.index(target) if target in nums else -1
Follow-ups interviewers ask
- With duplicates allowed (worst case O(n)).
- Find the rotation point itself.
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Search in a Rotated Sorted Array in Python?
The optimal solution runs in O(log n) time and O(1) auxiliary space. Each step discards half of the range.
What is the brute-force approach, and how do you optimise it?
Linear scan: O(n) time, O(1) space. Find the pivot, then binary search: O(log n) time, O(1) space. Two passes. One binary search: one half is always sorted: O(log n) time, O(1) space.
What follow-up questions do interviewers ask about Search in a Rotated Sorted Array?
With duplicates allowed (worst case O(n)). Find the rotation point itself.