Search in Rotated Sorted Array
The Prompt
There is an integer array `nums` sorted in ascending order (with distinct values). Prior to being passed to your function, `nums` is possibly rotated at an unknown pivot index `k`. Given the array `nums` after the possible rotation and an integer `target`, return the index of `target` if it is in `nums`, or `-1` if it is not in `nums`. You must write an algorithm with `O(log n)` runtime complexity.
Understanding the Problem
Plain binary search needs the whole range sorted so one comparison can discard half. A rotated array breaks that — but not completely: split any range at mid, and at least one of the two halves is still perfectly sorted (the cliff can only be in one of them).
That salvages binary search: identify the sorted half with one comparison (nums[left] <= nums[mid] means the left half is sorted), then use its endpoints to decide, definitively, whether the target lives inside it.
The Interview Flow
Interviewer
Now, let's search for a target in a rotated sorted array. Again, it must be O(log n).
Candidate
This is another modified binary search. Like finding the minimum, the key is to determine which half of the array is sorted at each step.
Interviewer
How do you do that?
Candidate
I'll use `left`, `right`, and `mid` pointers. In each iteration, I'll first check if the middle element is my target. If not, I need to figure out where to search next. I can check if the left half (from `left` to `mid`) is sorted by comparing `nums[left]` and `nums[mid]`.
Interviewer
Let's say the left half is sorted (`nums[left] <= nums[mid]`). What next?
Candidate
If the left half is sorted, I can then check if my `target` lies within the range of this sorted half (`nums[left] <= target < nums[mid]`). If it does, I search in the left half by setting `right = mid - 1`. If it doesn't, the target must be in the right, unsorted half, so I set `left = mid + 1`.
Interviewer
And what if the left half is not sorted?
Candidate
If the left half isn't sorted, it means the right half (from `mid` to `right`) must be sorted. I can then do a similar check: Does the `target` lie within the range of the sorted right half (`nums[mid] < target <= nums[right]`)? If yes, search right (`left = mid + 1`). Otherwise, search left (`right = mid - 1`).
Interviewer
That covers all cases. The logic is sound. Please implement it.
Why can we still discard half the array?
The invariant: if the target is present, it stays inside [left, right]. In the sorted half, the range check is exact — target in [nums[left], nums[mid]) means it must be there, so search that side; otherwise it certainly is not there, so search the other side. Either way, half the range is eliminated with certainty, never by guesswork.
One elimination per step keeps the O(log n) bound with O(1) space. The common pitfall is the range check: use <= on the boundary values (nums[left] <= target < nums[mid]) — off-by-one comparisons here are the classic bug interviewers watch for.
Modified Binary Search for Target
- Initialize `left = 0`, `right = nums.length - 1`.
- Loop while `left <= right`.
- Calculate `mid`. If `nums[mid] == target`, return `mid`.
- Determine which half is sorted. Check if `nums[left] <= nums[mid]`.
- **If left half is sorted:**
- Check if `target` is in the range `[nums[left], nums[mid])`.
- If yes, the target is in the left half, so `right = mid - 1`.
- If no, the target is in the right half, so `left = mid + 1`.
- **If right half is sorted:** (`nums[left] > nums[mid]`)
- Check if `target` is in the range `(nums[mid], nums[right]]`.
- If yes, the target is in the right half, so `left = mid + 1`.
- If no, the target is in the left half, so `right = mid - 1`.
- If the loop finishes without finding the target, return -1.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function search(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
return mid;
}
// Check if left half is sorted
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// Right half must be sorted
else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}Explanation
Search for target = 0 in nums = [4, 5, 6, 7, 0, 1, 2] — it lives at index 4.
1mid = 3, nums[3] = 7 != 0. nums[0] = 4 <= 7, so the left half [4, 5, 6, 7] is sorted. Is 0 in [4, 7)? No — discard it: lo = 4.
2mid = (4 + 6) / 2 = 5, nums[5] = 1 != 0. nums[4] = 0 <= 1, so the left half [0, 1] is sorted. Is 0 in [0, 1)? Yes: 0 <= 0 < 1 → hi = 4.
3lo = hi = 4, so mid = 4 and nums[4] = 0 == target. Return index 4 — three comparisons instead of a seven-element scan.
Complexity Analysis
TIME
O(log n)
SPACE
O(1)
Finished working through this one?
Mark it complete to track it on your Data Structures path.