Skip to main content

41. Search in Rotated Sorted Array

mediumAsked at Plaid

Search for a target in a sorted array that has been rotated. Plaid asks this because querying a circular buffer of transaction timestamps that wraps around a clock pivot is the same primitive.

By Alex Chen, 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^4
  • All values of nums are unique.
  • nums is an ascending array that is possibly rotated.
  • -10^4 <= target <= 10^4

Examples

Example 1

Input
nums = [4,5,6,7,0,1,2], target = 0
Output
4

Example 2

Input
nums = [4,5,6,7,0,1,2], target = 3
Output
-1

Approaches

1. Linear scan

Walk and check each.

Time
O(n)
Space
O(1)
function search(nums, target) {
  return nums.indexOf(target);
}

Tradeoff: Misses the O(log n) requirement.

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.

Output

Press Run or Cmd+Enter to execute

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).

Practice these live with InterviewChamp.AI

Drill Search in Rotated Sorted Array and other Plaid interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →