An ascending array of distinct integers nums was rotated at some unknown pivot, so that [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2].
Given the rotated array and an integer target, return the index of target, or -1 if it is not present. Your algorithm must run in O(log n) time.
Example
0 sits at index 4 in the rotated array.
Constraints
- 1 <= nums.length <= 5000
- -10^4 <= nums[i] <= 10^4
- All values of nums are unique.
- nums is an ascending array rotated at some pivot.
- -10^4 <= target <= 10^4
Intuition
The obvious approach ignores the rotation entirely and scans every element until it finds the target, returning its index or -1.
function search(nums, target) {
// Check each position in turn; the rotation doesn't matter to a linear scan.
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) return i;
}
return -1; // not present
}This is O(n) and throws away all the structure — the prompt wants O(log n). Can we do better?
The array isn't globally sorted, but a rotation has a key property: at any midpoint, at least one half is fully sorted (the pivot can only sit in one of them). Compare nums[lo] to nums[mid] to learn which half is the clean, sorted one. Then check whether target falls inside that sorted half's value range: if so, search there; if not, the target must be in the other half. Either way we discard half each step — ordinary binary search, just with a which-half-is-sorted test layered on top.
This uses the inclusive lo <= hi exact-match shape (returning mid on a hit), not the half-open boundary form — we want a specific value, not a boundary.
Walking it through:
nums = [4, 5, 6, 7, 0, 1, 2], target = 0
mid = 3 (value 7). The left half [4,5,6,7] is sorted, but 0 isn't inside its range — so search the right.
Now [4, 6], mid = 5 (value 1). The left half [0,1] is sorted and 0 falls in [0,1) — discard the right.
Range collapses to index 4, whose value is exactly 0. Found at index 4.
Had the target been 3, every half-check would exclude it and the pointers would cross, returning -1.
Optimization
One-pass binary search on the sorted half
At each step the midpoint splits the array into two halves, and at least one of them is fully sorted (no pivot inside it). Compare nums[mid] to nums[lo] to learn which half is sorted, then check whether target falls inside that sorted half's value range: if so, search there; otherwise search the other half. This halves the search each iteration.
O(log n) time, O(1) space.
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]) {
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}Complexity analysis
Time complexity: O(log n). Here's why:
- Each step computes one midpoint, decides which half is sorted, and discards the half that can't hold the target.
- The which-half-is-sorted test is O(1), so the range still halves every iteration.
So the search runs about log₂ n times — overall O(log n).
Space complexity: O(1). Here's why:
- Only the
lo/hi/midintegers are tracked; the input isn't copied or re-sorted.
No structure grows with n — overall O(1).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| nums = [], target = 5 | -1 | Empty array — nothing to find. |
| nums = [3], target = 3 | 0 | Single element equal to the target. |
| nums = [1,2,3,4,5], target = 4 | 3 | Not actually rotated — degrades to ordinary binary search. |
| nums = [6,7,1,2,3], target = 1 | 2 | Target sits just past the pivot, in the rotated suffix. |
| nums = [4,5,6,7,0,1,2], target = 8 | -1 | Target larger than every element — absent. |
| nums = [7,8,1,2,3], target = 7 | 0 | Target is the rotation's largest value, at the front. |
Try it yourself
Write your solution against the real judge before checking the reference.