March 24
Search in Rotated Sorted Array
How to adapt binary search when the full order is broken by a rotation but not completely gone.
Search Intermediate 22 min TypeScript
Given an array of distinct integers nums, sorted in ascending order and then rotated at an unknown pivot, return the index of target.
If target does not exist, return -1.
Your solution must run in O(log n).
Example:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
What to notice before coding
- Rotation did not destroy all order. It only created a cut.
- At each iteration, one half is still normally sorted.
- The decision is not only about comparing `target` with `nums[mid]`. You also need the half boundaries.
Common mistakes
- treating it like normal binary search and moving to the wrong side
- forgetting to identify which half is sorted before deciding
Step 1 - Understand what rotation changed
Before rotation, normal binary search works because the whole array is sorted.
After rotation, the whole array no longer looks sorted:
[4, 5, 6, 7, 0, 1, 2]
But it is not random either.
There are still sorted pieces. The new job is figuring out which side keeps the order at each step.
Step 2 - Write the most direct baseline
The baseline is simple:
- scan the array
- compare each value with
target
It works.
But it throws away the main clue in the problem: the input is still almost sorted.
Step 3 - Ask what remains true
Pick a mid.
Even after rotation, one of these halves must still be sorted:
- left:
nums[left]..nums[mid] - right:
nums[mid]..nums[right]
If the left side is sorted, you decide:
- is
targetinside that interval? - if yes, go left
- if not, go right
If the right side is sorted, do the same reasoning there.
Step 4 - The real insight
Standard binary search asks:
- is
targetlarger or smaller thannums[mid]?
Here that is not enough.
The correct question becomes:
- which half is sorted?
- does the target belong in it?
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function search(nums: number[], target: number): number {
// your solution here
return -1
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(log n)
Space: O(1)
Solution 1 - Linear scan
Good baseline because it makes the wasted structure obvious.
export function search(nums: number[], target: number): number {
for (let index = 0; index < nums.length; index += 1) {
if (nums[index] === target) {
return index
}
}
return -1
}It works, but it costs O(n) and ignores the point of the problem.
Solution 2 - Adapted binary search
Now you use the sorted half as the decision rule.
export function search(nums: number[], target: number): number {
let left = 0
let right = nums.length - 1
while (left <= right) {
const mid = Math.floor((left + right) / 2)
if (nums[mid] === target) {
return mid
}
if (nums[left] <= nums[mid]) {
const targetIsOnLeft = nums[left] <= target && target < nums[mid]
if (targetIsOnLeft) {
right = mid - 1
} else {
left = mid + 1
}
} else {
const targetIsOnRight = nums[mid] < target && target <= nums[right]
if (targetIsOnRight) {
left = mid + 1
} else {
right = mid - 1
}
}
}
return -1
}The central idea is simple: use the order that survived to cut half of the search space.
What to say in the interview
A strong short explanation would be:
The baseline would scan in
O(n). The stronger version still usesbinary search, but before choosing a side I first identify which half is sorted. Then I check whether the target fits inside that sorted interval or the other one. That way I can keep discarding half of the array each time.
That shows that you:
- did not just memorize the standard template
- understood what rotation changes and what it does not
- used interval boundaries to justify the cut
When this pattern shows up again
This pattern comes back when you need to:
- adapt
binary searchto almost-sorted input - decide based on local invariants
- use the remaining ordered region instead of giving up to a full scan
The point is not memorizing the rotated case.
The point is learning to look for the property that still survives.