Find a value in a rotated sorted array
An array of distinct integers was sorted in increasing order and then rotated at an unknown
point, so [0, 1, 2, 4, 5, 6, 7] might arrive as [4, 5, 6, 7, 0, 1, 2]. Given the rotated
array and a target, return the index of target, or −1 if it is absent. Use
O(log n) comparisons.
Examples
| Input | Output | Why |
|---|---|---|
nums = [4, 5, 6, 7, 0, 1, 2], target = 0 | 4 | |
nums = [4, 5, 6, 7, 0, 1, 2], target = 3 | -1 | |
nums = [1], target = 0 | -1 |
Constraints
- 1 ≤ n ≤ 5000
- −10⁴ ≤ nums[i], target ≤ 10⁴
- All values are distinct
Hints
Hint 1
Comparing target with nums[mid] alone no longer tells you which side to keep. What else does the middle tell you?
Hint 2
The rotation point lies on at most one side of mid, so at least one of nums[lo..mid] and nums[mid..hi] is sorted. Compare nums[lo] with nums[mid] to see which.
Hint 3
For the sorted side you can test "is target between its ends?" exactly. If yes, search there; if no, search the other side.
Where people lose marks
- Writing nums[lo] < nums[mid] instead of ≤: when lo = mid the left half is one element and is sorted.
- Testing the unsorted half with a range check: its values are not the ones between its ends.
- Mixing strict and non-strict bounds so that target = nums[mid] or target = nums[lo] falls through both tests.
Dry run on [15,18,22,27,31,2,5,8,11],8
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 4target8
Looking for 8. The array was sorted and then rotated: it climbs, breaks once, and climbs again.
-
Step 2 / 4lo0mid4hi8
nums[0] = 15 ≤ nums[4] = 31, so the left half is sorted and holds exactly the values from 15 to 31. 8 is not in that range, so it can only be on the right: lo = 5.
-
Step 3 / 4lo5mid6hi8
nums[5] = 2 ≤ nums[6] = 5, so the left half is sorted and holds exactly the values from 2 to 5. 8 is not in that range, so it can only be on the right: lo = 7.
-
Step 4 / 4lo7mid7hi8
nums[7] = 8. Return 7.
How to think about it
A rotated sorted array has one break, the place where a large value is followed by a small one. Cut any
range [lo, hi] at mid and the break falls in at most one of the two halves, so at least
one half is sorted, and one comparison says which:
- If
nums[lo] ≤ nums[mid], the left halfnums[lo..mid]is sorted. The target is in it exactly whennums[lo] ≤ target < nums[mid]. If so,hi = mid − 1; otherwiselo = mid + 1. - Otherwise the right half
nums[mid..hi]is sorted. The target is in it exactly whennums[mid] < target ≤ nums[hi]. If so,lo = mid + 1; otherwisehi = mid − 1.
We never need to know where the break is. We only need a half whose contents we can describe exactly, and the sorted half is such a half: its values are precisely those between its two ends.
The alternative is two searches: find the rotation point with the minimum search, then run an ordinary search on the side that can contain the target. Also O(log n), and easier to get right if the single-pass conditions do not come to you under pressure.
Complexity. Time O(log n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def search_rotated(nums, target):
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 nums[lo..mid] is sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half nums[mid..hi] is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1#include <vector>
int solve(const std::vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
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;
}class Solution {
public int searchRotated(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
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;
}
}function searchRotated(nums, target) {
let lo = 0, hi = nums.length - 1;
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 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;
}fn solve(nums: &[i64], target: i64) -> i64 {
// signed indices, so that hi = mid - 1 may fall below zero and end the loop
let (mut lo, mut hi) = (0i64, nums.len() as i64 - 1);
while lo <= hi {
let mid = lo + (hi - lo) / 2;
let (l, m, h) = (nums[lo as usize], nums[mid as usize], nums[hi as usize]);
if m == target {
return mid;
}
if l <= m { // left half is sorted
if l <= target && target < m { hi = mid - 1 } else { lo = mid + 1 }
} else { // right half is sorted
if m < target && target <= h { lo = mid + 1 } else { hi = mid - 1 }
}
}
-1
}import Data.Array
solve :: [Int] -> Int -> Int
solve nums target = go 0 (n - 1)
where
n = length nums
a = listArray (0, n - 1) nums
go lo hi
| lo > hi = -1
| m == target = mid
| l <= m = if l <= target && target < m then go lo (mid - 1) else go (mid + 1) hi -- left half sorted
| otherwise = if m < target && target <= h then go (mid + 1) hi else go lo (mid - 1) -- right half sorted
where
mid = lo + (hi - lo) `div` 2
(l, m, h) = (a ! lo, a ! mid, a ! hi)Variants to try
- Values may repeat: when nums[lo] = nums[mid] = nums[hi] neither half can be identified, and the search may have to step past one element.
- Return the number of positions the array was rotated by: the index of the minimum.
Next problems
Minimum of a rotated sorted array
The input is not sorted, so the usual comparison is useless. Compare against the right end instead.
Open the problem → Medium20 minSearch a rotated array with repeated values
When the two ends and the middle are equal, no comparison can say which half is sorted. Shrink both ends by one and carry on.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem →Write a solution and run it against the real test table.
Keep going
Minimum of a rotated sorted array
The input is not sorted, so the usual comparison is useless. Compare against the right end instead.
Open the problem → Medium20 minSearch a rotated array with repeated values
When the two ends and the middle are equal, no comparison can say which half is sorted. Shrink both ends by one and carry on.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.