Binary Search · LC #33
Search in Rotated Sorted Array
A sorted array has been rotated at an unknown pivot; given a target, return its index or -1. Must run in O(log n) - requires identifying which half is sorted at each step.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
There is an integer array `nums` sorted in ascending order (with distinct values). Prior to passing 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. You must write an algorithm with O(log n) runtime complexity.
Sample I/O
Input: nums=[4,5,6,7,0,1,2], target=0 Output: 4 Input: nums=[4,5,6,7,0,1,2], target=3 Output: -1 Input: nums=[1], target=0 Output: -1
Time: O(log n) · Space: O(1)
Intuition
How to Think About It
Intuition
Even after rotation, at least one of the two halves defined by `mid` is always fully sorted. By checking which half is sorted and whether target falls within it, we can eliminate half the search space each iteration - preserving O(log n).
Core Concept
At each step: (1) check if left half `[l..mid]` is sorted via `nums[l] <= nums[mid]`. (2) If sorted and target is within `[nums[l], nums[mid])`, search left; else search right. (3) Otherwise right half `[mid..r]` is sorted; if target within `(nums[mid], nums[r]]`, search right; else search left. One half is always sorted because rotation creates exactly one "break point".
When to use
Searching in a rotated or "mountain" sorted array; any scenario where an otherwise sorted structure has a single discontinuity.
When NOT to use
When the array has duplicates - the `nums[l] <= nums[mid]` check becomes ambiguous; LC 81 (with duplicates) requires worst-case O(n).
Key Insights
What to Know Cold
- Exactly one of the two halves produced by mid is always sorted; this is the key invariant enabling O(log n).
- Use `nums[l] <= nums[mid]` (not `<`) to correctly handle the case where l == mid (single element left half).
- After identifying the sorted half, use strict range checks (`target >= nums[l] && target < nums[mid]`) to decide direction.
- The rotation point is irrelevant - you never need to find it explicitly.
- Fails with duplicates: if `nums[l] == nums[mid]`, you cannot determine which half is sorted → must fall back to `l++`.
3 examples
Worked Examples
Target in rotated right half
nums=[4,5,6,7,0,1,2], target=0.
l=0,r=6. mid=3→nums[3]=7. Left [4..7] sorted, 0 not in [4,7) → l=4. mid=5→nums[5]=1. Left [0..1] sorted, 0 in [0,1) → r=4. mid=4→nums[4]=0 → return 4.
function search(nums: number[], target: number): number {
let l=0,r=nums.length-1;
while(l<=r){
const m=l+Math.floor((r-l)/2);
if(nums[m]===target) return m;
if(nums[l]<=nums[m]){
if(target>=nums[l]&&target<nums[m]) r=m-1;
else l=m+1;
} else {
if(target>nums[m]&&target<=nums[r]) l=m+1;
else r=m-1;
}
}
return -1;
}Output: 4
Core case: target is in the unsorted-looking half; the sorted-half check routes correctly.
Target absent
nums=[4,5,6,7,0,1,2], target=3.
Binary search exhausts both halves without finding 3; returns -1.
Output: -1
Validates correct termination on a miss in rotated array.
No rotation (pivot=0)
nums=[1,2,3,4,5], target=3.
nums[l]<=nums[mid] always true (no break point); degrades to standard binary search.
Output: 2
Shows algorithm handles unrotated arrays without modification.