Search in Rotated Sorted Array
Problem
[0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Given the
rotated array nums and a target, return the index of
target, or -1 if it is missing, in O(log n) time.[4,5,6,7,0,1,2], t=0Output4[4,5,6,7,0,1,2], t=3Output-1[1], t=0Output-11 ≤ n ≤ 5000 · -104 ≤ nums[i], target ≤ 104 · all values distinct · Required: O(log n).
Try it yourself
class Solution {
public int search(int[] nums, int target) {
}
}
mid and at least one half is
normally sorted. A range check on that sorted half tells you for certain whether the
target can be there — otherwise discard it.Instinct Sorted data, a rotated array, or find the min/max X that works where a yes/no test flips only once - halve the search space every step.
Memory hack Find the fence - every candidate reads NO NO NO YES YES, and binary search just walks to where the fence stands.
Open the Binary Search guide →Approaches
Brute ForceLinear Search
O(n)Space O(1)Check every element until one equals target. Works on any array,
rotated or not, because it never relies on order.
public int search(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { if (nums[i] == target) return i; } return -1; }
Correct and simple, but ignores the structure and misses the O(log n) bar.
BetterFind Pivot, then Binary Search
O(log n)Space O(1)First binary-search the pivot (index of the minimum): if
nums[mid] > nums[right] the drop lies right of mid.
The array is then two sorted runs [0..pivot-1] and
[pivot..n-1]; pick the run whose range holds target and do
a standard binary search there.
public int search(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left < right) { // find index of the minimum int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) left = mid + 1; else right = mid; } int pivot = left; left = 0; right = nums.length - 1; if (target >= nums[pivot] && target <= nums[right]) left = pivot; else right = pivot - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; if (nums[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }
Meets O(log n), but needs two separate binary searches.
OptimalOne-Pass Modified Binary Search
O(log n)Space O(1)At each step decide which half is sorted: if
nums[left] ≤ nums[mid] the left half is. If target
lies inside that sorted half's range, search it; otherwise go to the other half.
Every iteration still halves the window.
public int search(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; if (nums[left] <= nums[mid]) { // left half sorted if (nums[left] <= target && target < nums[mid]) right = mid - 1; else left = mid + 1; } else { // right half sorted if (nums[mid] < target && target <= nums[right]) left = mid + 1; else right = mid - 1; } } return -1; }
Dry run[4,5,6,7,0,1,2], t=0
- 14l567m012r[4..7] sorted, 0 out → l=4
- 245670l1m2r[0..1] sorted, 0 in → r=4
- 345670l r m12nums[4]=0 → return 4 ✔
Single binary search, no pivot pass — the expected interview answer.
nums[l]==nums[m]==nums[r] is
ambiguous — shrink both ends; worst case becomes O(n).At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Linear Search | O(n) | O(1) |
| Better | Find Pivot, then Binary Search | O(log n) | O(1) |
| Optimal | One-Pass Modified Binary Search | O(log n) | O(1) |
- Using
nums[left] < nums[mid]— fails whenleft == mid(2-element window). - Mixing strict and non-strict bounds in the range check — misses targets at the edges.
- Pivot version: forgetting the un-rotated case (
pivot = 0, left run is empty).
- Draw the array as two ascending “ramps” to show one half is always sorted.
- Mention the pivot approach first, then fold it into one pass.
- Test: not rotated, rotated by n-1, single element, target at the pivot.