Search in Rotated Sorted Array
Find a target in a sorted array that has been rotated at an unknown point, in O(log n). A test of whether you can adapt binary search when only half the range is sorted. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given an array nums of distinct integers that was sorted in increasing order and then rotated: some prefix was cut off and moved to the end. For example, [10, 20, 30, 40, 50] rotated after its second element becomes [30, 40, 50, 10, 20]. The rotation point is unknown, and the array may not be rotated at all.
Return the index of target in nums, or -1 if it isn't there. Your solution should run in O(log n) time.
Example 1
- Input
- nums = [15, 18, 22, 3, 7, 11], target = 7
- Output
- 4
The array was rotated so that 3 is the smallest value; 7 sits at index 4.
Example 2
- Input
- nums = [9, 12, 1, 4], target = 10
- Output
- -1
10 falls between values in the array but is not one of them.
Example 3
- Input
- nums = [30, 40, 50, 10, 20], target = 40
- Output
- 1
Constraints
- 1 ≤ nums.length ≤ 5000
- -10⁴ ≤ nums[i], target ≤ 10⁴
- All values in nums are distinct.
- nums is an increasing array, possibly rotated.
Practice
Runs 13 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Search in Rotated Sorted Array in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Search in Rotated Sorted Array
Pattern: Binary search on the sorted half
"Sorted" plus "O(log n)" means binary search, but the rotation breaks the usual rule that everything left of mid is smaller. The fix comes from one observation: if you split a rotated array at any point, at least one of the two halves is still fully sorted.
You can tell which half is sorted by comparing the ends. If nums[lo] ≤ nums[mid], the left half has no break in it. Once you know a half is sorted, checking whether target lies inside it is a simple range test on its two endpoints. If it does, search there; if not, it must be in the other half. Each step still throws away half the range.
Approach 1: Linear scan
Walk the array and return the index where nums[i] == target. Always correct, but it ignores the sortedness entirely and misses the time requirement.
Time O(n) · Space O(1)
Approach 2: Find the rotation point, then binary search
First binary search for the index of the minimum (the spot where nums[i] < nums[i - 1]), comparing nums[mid] with nums[hi]. That splits the array into two sorted runs. Pick the run whose range covers target and run an ordinary binary search on it. Two passes, both logarithmic, and easy to reason about.
Time O(log n) · Space O(1)
Approach 3: Single binary search on the sorted half
Keep lo and hi. While lo ≤ hi:
- Compute
mid. Ifnums[mid] == target, returnmid. - If
nums[lo] ≤ nums[mid], the left half is sorted. Ifnums[lo] ≤ target < nums[mid], movehi = mid - 1; otherwiselo = mid + 1. - Otherwise the right half is sorted. If
nums[mid] < target ≤ nums[hi], movelo = mid + 1; otherwisehi = mid - 1.
Return -1 when the range is empty.
Time O(log n) · Space O(1)
| Approach | Time | Space |
|---|---|---|
| Linear scan | O(n) | O(1) |
| Find the rotation point, then binary search | O(log n) | O(1) |
| Single binary search on the sorted half | O(log n) | O(1) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Search in Rotated Sorted Array solution in Python
def search(nums: list[int], target: int) -> int:
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 -1Search in Rotated Sorted Array solution in JavaScript
function search(nums, target) {
let lo = 0;
let hi = nums.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] === target) return mid;
if (nums[lo] <= nums[mid]) {
// left half is sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
// right half is sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}Common mistakes
- Using `<` instead of `≤` in `nums[lo] ≤ nums[mid]`. When `lo == mid` the one-element left half is sorted, and a strict comparison sends you the wrong way on two-element arrays like `[2, 1]`.
- Making both range checks inclusive on the `mid` side. You already know `nums[mid] != target`, so the bounds should exclude it.
- Assuming the array is always rotated. An unrotated array is just the case where the left half is always sorted, and the code must still handle it.
- Trying to apply this to arrays with duplicates. With repeated values, `nums[lo] == nums[mid]` no longer tells you which half is sorted.
What interviewers look for
State the key fact before you write anything: "at least one half around mid is sorted, and I can tell which by comparing nums[lo] with nums[mid]." Interviewers are listening for that sentence, because everything else is ordinary binary search.
Then trace a small rotated case and the unrotated case out loud, and include a two-element array. Most bugs in this problem are off-by-one errors in the range checks, and a quick trace of [2, 1] catches them.
Follow-up questions
What if the array can contain duplicates?
When `nums[lo] == nums[mid] == nums[hi]` you cannot tell which half is sorted, so shrink the range by one (`lo += 1`, `hi -= 1`) and continue. Worst case degrades to O(n), for example an array of all equal values with one different element.
How would you find the minimum element or the rotation count?
Binary search comparing `nums[mid]` with `nums[hi]`: if `nums[mid] > nums[hi]` the minimum is to the right of `mid`, otherwise it is at `mid` or to its left. The index of the minimum is also the number of positions the array was rotated.
Can you do it with a standard library binary search?
Yes: find the rotation point first, then call `bisect_left` (or your own lower-bound) on whichever sorted run could contain the target, and adjust the index by the run offset.
Companies that ask Search in Rotated Sorted Array
Search in Rotated Sorted Array is tagged by 149 companies in our interview dataset. The score shows how often it comes up at each company.
- Toyota Usa100%
- Sojern100%
- Nylas100%
- Delhivery100%
- UPS98%
- Freelancercom97%
- Samcart94%
- Tinkoff93.8%
- Walmart Labs91.3%
- Epic91%
- Canva90%
- Grammarly89.1%
- Biontech89%
- Getyourguide89%
- Cohesity87.9%
- Dp World87.6%
- Twist Bioscience87%
- Autodesk87%
- Softserve85%
- Chamberlain Group83%
- Siriusxm83%
- Cerner83%
- Latitude Ai83%
- Costar Group82%
and 125 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required