#33 Search in Rotated Sorted Array
frequently reported atWalmartByteDance / TikTokAmazonNVIDIABloombergMicrosoft
the problem
In plain words
A sorted array of distinct values was rotated at an unknown pivot (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Return the index of target or −1, in O(log n).
in nums = [4,5,6,7,0,1,2], target = 0
out 4
in nums = [4,5,6,7,0,1,2], target = 3
out -1
in nums = [1], target = 0
out -1
- 1 ≤ n ≤ 5000
- -10⁴ ≤ nums[i], target ≤ 10⁴
- All values distinct
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternModified binary search
Split at mid and at least one half is fully sorted. For a sorted half you can tell instantly whether the target lies inside it; if not, it's in the other half.
solutions
From brute force to optimal
Ignore the structure and look everywhere.
- Return the first i with nums[i] == target, else −1.
Every element once.
One index.
class Solution { public int search(int[] nums, int target) { for (int i = 0; i < nums.length; i++) if (nums[i] == target) return i; return -1; }}Binary search the minimum's index; the two pieces around it are each sorted.
- pivot = index of the minimum (compare mid with hi).
- If nums[pivot] ≤ target ≤ nums[n−1] search [pivot, n−1].
- Else search [0, pivot−1].
Two binary searches.
A few integers.
class Solution { public int search(int[] nums, int target) { int n = nums.length; int lo = 0, hi = n - 1; while (lo < hi) { // 1) find the index of the minimum int mid = lo + (hi - lo) / 2; if (nums[mid] > nums[hi]) lo = mid + 1; else hi = mid; } int pivot = lo; // 2) [pivot..n-1] and [0..pivot-1] are both sorted: pick the one that can hold target if (target >= nums[pivot] && target <= nums[n - 1]) return binary(nums, pivot, n - 1, target); return binary(nums, 0, pivot - 1, target); } private int binary(int[] a, int lo, int hi, int target) { while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] == target) return mid; if (a[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; }}At each mid, decide which half is sorted, then whether the target fits in it.
- nums[mid] == target → done.
- If nums[lo] ≤ nums[mid], left is sorted: target in [nums[lo], nums[mid]) → go left, else go right.
- Otherwise right is sorted: target in (nums[mid], nums[hi]] → go right, else go left.
Each step discards half.
Three indices.
class Solution { public int search(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 [lo..mid] is sorted if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; // target is inside it else lo = mid + 1; // target must be on the right } else { // right half [mid..hi] is sorted if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; // target is inside it else hi = mid - 1; // target must be on the left } } return -1; }}Dry run
in the room
How to say it in the interview
talk track
- Draw the array as two rising slopes with a cliff — it makes "one half is sorted" obvious.
- Explain why it's
nums[lo] <= nums[mid](with=): when lo == mid the left half is one element, which is sorted.
traps
- Using
<instead of<=innums[lo] <= nums[mid]— fails on 2-element arrays like [3,1]. - Strict vs non-strict bounds when testing whether the target lies in the sorted half.
what they ask next
Follow-ups
With duplicates (LC 81)?
When nums[lo] == nums[mid] == nums[hi] you can't tell which half is sorted; shrink with lo++ (and hi--). Worst case becomes O(n).
before you submit
Edge cases to test
- Two elements like [3, 1] — this is where
<=in nums[lo] <= nums[mid] matters. - No rotation at all: [1, 2, 3, 4, 5, 6].
- Target right at the cliff: the largest or the smallest value.
practise next
Similar problems
- #153Find Minimum in Rotated Sorted ArrayMediumin Binary Search
- #162Find Peak ElementMediumin Binary Search