41. Search in Rotated Sorted Array
mediumAsked at PlaidGiven a rotated sorted array — pivot unknown, values distinct — return a target's index in O(log n), or -1 if absent. Plaid candidates report this medium in backend screens, where a fintech ledger gives it a natural home: ring buffers of timestamped transactions wrap exactly like rotated arrays, and finding an entry fast means binary-searching across the wrap point. The question cleanly separates candidates who understand WHY binary search survives rotation (one half is always sorted) from those who only memorized the template.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Plaid loops.
- Glassdoor (2025)— Plaid backend onsite — circular-buffer variant.
- Blind (2026)— Plaid SWE II OA.
Problem
There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]. 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 in nums. You must write an algorithm with O(log n) runtime complexity.
Constraints
1 <= nums.length <= 5000-10^4 <= nums[i] <= 10^4All values of nums are unique.nums is an ascending array that is possibly rotated.-10^4 <= target <= 10^4
Examples
Example 1
nums = [4,5,6,7,0,1,2], target = 04Explanation: The array was rotated at the 7-to-0 cliff. Binary search still works: at mid = 7 the left half [4..7] is sorted and 0 is outside it, so the search correctly jumps right.
Example 2
nums = [4,5,6,7,0,1,2], target = 3-1Explanation: 3 falls inside the value gap created by the rotation cliff — the loop exhausts lo > hi without a hit and returns -1.
Approaches
1. Linear scan
Walk and check each.
- Time
- O(n)
- Space
- O(1)
function search(nums, target) {
return nums.indexOf(target);
}Tradeoff: Correct in one line but ignores the explicit O(log n) requirement in the problem statement — on this question the linear scan is not a warm-up, it is a red flag. Mention it only to contrast against the invariant that makes binary search survivable under rotation.
2. Modified binary search
At each midpoint, exactly one of [lo..mid] and [mid..hi] is sorted. Check which half is sorted, then decide which half contains the target.
- Time
- O(log n)
- Space
- O(1)
function search(nums, target) {
let lo = 0, hi = nums.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] === target) return mid;
if (nums[lo] <= nums[mid]) {
// left half sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
// right half sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}Tradeoff: Logarithmic. The trick is identifying which half is sorted (the half whose endpoints are in order) before deciding the search direction.
Plaid-specific tips
Plaid grades this on whether you identify the 'one half is always sorted' invariant. Bonus signal: state out loud 'either nums[lo..mid] is sorted or nums[mid..hi] is sorted, never both un-sorted.' That's the key observation that makes binary search work despite the rotation.
Common mistakes
- Using < instead of <= when checking nums[lo] vs nums[mid] — misses the edge case where lo == mid.
- Checking target ranges with the wrong bounds (off by one on inclusive/exclusive).
- Trying to find the pivot first then doing two binary searches — works but more code.
Follow-up questions
An interviewer at Plaid may pivot to one of these next:
- Allow duplicates (LC 81) — worst case O(n) due to ambiguous halves.
- Find the minimum in rotated sorted array (LC 153).
- Find rotation count.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is exactly one half always sorted?
Rotation creates exactly one 'cliff.' The midpoint falls on one side of the cliff, so the side without the cliff is monotonically sorted.
What if duplicates are allowed?
When nums[lo] == nums[mid] == nums[hi], you can't tell which half is sorted. You have to shrink lo and hi by one, making worst case O(n).
Why not locate the pivot first, then binary-search the correct half?
It works and is also O(log n) — two searches instead of one. Interviewers accept it, but the single-pass version demonstrates the deeper insight (one half is ALWAYS sorted), uses less code, and avoids stitching index offsets across the two halves.