Search in Rotated Sorted Array
Problem statement
You're given a list of distinct integers that started out sorted in ascending order, then got "rotated": some number of values from the front were cut off and moved to the end. For example, [0, 1, 2, 4, 5, 6, 7] rotated by 3 becomes [4, 5, 6, 7, 0, 1, 2].
Given the rotated list and a target value, return the index of target, or -1 if it isn't there.
Your algorithm has to run in O(log n) time — a rotation doesn't give you permission to fall back to a plain scan.
Examples
Example 1
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Explanation: 0 sits at index 4 in the rotated list.
Example 2
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
Explanation: 3 never appears in the list.
Example 3
Input: nums = [1], target = 0
Output: -1
Explanation: With only one value in the list, and it isn't 0, the answer is -1.
Hints
Approach
Optimal: One-pass modified binary search
Intuition
Better does two separate searches. This approach folds both jobs into one loop: at every step, first check which half around mid is the normally sorted one (the left half is sorted exactly when nums[left] <= nums[mid]), then check whether target falls inside that sorted half's range. If it does, keep searching there; if it doesn't, target must be in the other half, so search that one instead. No separate pivot step, no second search — one loop does the whole job.
Steps
- Set
left = 0,right = len(nums) - 1. - While
left <= right: computemid. Ifnums[mid] == target, returnmid. - If
nums[left] <= nums[mid], the left half[left, mid]is sorted normally. Iftargetis betweennums[left]andnums[mid](exclusive ofmid, which we already ruled out), search left:right = mid - 1. Otherwise search right:left = mid + 1. - Otherwise the right half
[mid, right]is the sorted one. Iftargetis betweennums[mid]andnums[right], search right:left = mid + 1. Otherwise search left:right = mid - 1. - If the loop ends without returning,
targetisn't present — return-1.
Dry run
nums = [4, 5, 6, 7, 0, 1, 2], target = 0
| step | left | right | mid | nums[mid] | which half is sorted? | action |
|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 7 | left [4,5,6,7] (nums[0]=4 ≤ 7) |
0 not in [4, 7) → search right: left = 4 |
| 2 | 4 | 6 | 5 | 1 | left [0,1] (nums[4]=0 ≤ 1) |
0 is in [0, 1) → search left: right = 4 |
| 3 | 4 | 4 | 4 | 0 | — | nums[4] == 0 → return 4 |
Edge cases: an array that isn't rotated at all (already fully sorted) still works, since one comparison always finds nums[left] <= nums[mid] true and the logic reduces to a normal binary search.
Complexity
Time O(log n) - A single binary search loop; each step still throws away half of what's left, so it takes about log₂(n) steps to finish.
Space O(1) - Just `left`, `right` and `mid`.
class Solution:
def search(self, nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
if __name__ == "__main__":
print(Solution().search([4, 5, 6, 7, 0, 1, 2], 0)) # 4
print(Solution().search([4, 5, 6, 7, 0, 1, 2], 3)) # -1
print(Solution().search([1], 0)) # -1RecapThe whole problem in a few lines, for the night before
- Spot it: "rotated sorted array, find a value in O(log n)" — one half around any midpoint is always normally sorted
- Idea: at each step, work out which half is sorted, then check if
targetfalls in that half's range to decide which side to keep searching - Cost: O(log n) time, O(1) space
- Trap: forgetting the range check is exclusive on the
midend but inclusive on the near end — mixing that up double-counts or skips the midpoint
Interview follow-ups
What if the array can contain duplicate values?
Duplicates break the trick used to decide which half is sorted: if
nums[left] == nums[mid] == nums[right], you genuinely can't tell which side holds the break. The fix is to shrink both ends inward by one (left += 1,right -= 1) whenever that ambiguous case comes up, and fall back to the same logic otherwise. This can push the worst case to O(n) — imagine an array of all the same value with one different value hidden somewhere — but it stays O(log n) on average.The array is too large to hold in memory, but you can still do O(1) reads at any index. How would you adapt the search?
Nothing about the algorithm changes — it never needs more than three index positions (
left,mid,right) at a time, so it works unchanged against a data source that only supports "read the value at this position," such as a memory-mapped file or a remote array behind an API, as long as each read stays cheap.
Frequently asked questions
Compare the value at left with the value at mid. If nums[left] <= nums[mid], nothing broke the ascending order between those two points, so the left half is sorted normally. If it's the other way around (nums[left] > nums[mid]), the rotation's break must be somewhere inside the left half, which means the right half — from mid to right — is the one that's still sorted.
Because the range check decides which half to search next, and mid itself has already been ruled out as a match by that point. Treating the range as [nums[left], nums[mid]) — including the low end, excluding mid — keeps the two halves from overlapping or missing a value, so every index gets checked exactly once across the whole search.
That's exactly what the Better approach does — finding the minimum is the same as finding the pivot. It's a perfectly valid way to think about the problem and is easier to reason about with pen and paper. The optimal approach is a compressed version of the same idea, worth knowing because interviewers often ask for the single-loop version once you've explained the two-step one.
A circular buffer of timestamped events (like a ring buffer of recent log lines or metric samples) is sorted by time but wraps around, so the oldest and newest entries sit next to each other in memory even though they're far apart in time — searching it for a specific timestamp is exactly this problem.
