Skip to main content

33. Search in Rotated Sorted Array

mediumAsked at Robinhood

Given a rotated sorted array, find a target value in O(log n). Robinhood asks this as the natural follow-up to binary search — they want to see the modified binary-search that identifies the sorted half first.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Robinhood loops.

  • Glassdoor (2026-Q1)— Robinhood SWE phone-screen reports list Search in Rotated Sorted Array as a recurring binary-search variant.
  • Blind (2025-11)— Robinhood new-grad trip reports cite this and Find Minimum in Rotated Sorted Array as a paired sequence.

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 (1 <= k < nums.length). 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. 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

Example 3

Input
nums = [1], target = 0
Output
-1

Approaches

1. Find pivot then binary search

Binary search for the rotation pivot. Then binary search the appropriate half.

Time
O(log n)
Space
O(1)
function searchTwoPass(nums, target) {
  function findPivot() {
    let lo = 0, hi = nums.length - 1;
    while (lo < hi) {
      const mid = lo + ((hi - lo) >> 1);
      if (nums[mid] > nums[hi]) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }
  function bsearch(lo, hi) {
    while (lo <= hi) {
      const mid = lo + ((hi - lo) >> 1);
      if (nums[mid] === target) return mid;
      if (nums[mid] < target) lo = mid + 1;
      else hi = mid - 1;
    }
    return -1;
  }
  const pivot = findPivot();
  if (target >= nums[pivot] && target <= nums[nums.length - 1]) return bsearch(pivot, nums.length - 1);
  return bsearch(0, pivot - 1);
}

Tradeoff: Two passes of binary search — O(log n) overall but more code. Use if you want to teach the rotation-pivot concept; combined version is cleaner.

2. Modified binary search (optimal)

At each step, one half [lo..mid] or [mid..hi] is sorted. Check which, then check if target is in the sorted half's range; recurse accordingly.

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 - lo) >> 1);
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {
      // Left half is sorted
      if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      // Right half is sorted
      if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

Tradeoff: One pass. The invariant 'at each step exactly one half is sorted' is what makes binary search still applicable on rotated input.

Robinhood-specific tips

Robinhood interviewers want the single-pass modified binary search. Articulate the invariant out loud: 'one half is always sorted; I check which by comparing nums[lo] and nums[mid].' Walk through a small rotation example (4 nodes) to verify your boundary conditions. The follow-up is almost always LC 81 (duplicates allowed) — be ready to discuss why that changes the complexity to O(n) worst case.

Common mistakes

  • Using nums[lo] < nums[mid] (strict) instead of nums[lo] <= nums[mid] — fails when lo == mid (single-element half).
  • Off-by-one on the in-range check: target >= nums[lo] vs target > nums[lo]. Use >= because the bound is inclusive.
  • Forgetting to check nums[mid] === target first — wastes a comparison.

Follow-up questions

An interviewer at Robinhood may pivot to one of these next:

  • Search in Rotated Sorted Array II (LC 81) — duplicates allowed; degrades to O(n) in pathological cases.
  • Find Minimum in Rotated Sorted Array (LC 153) — find the pivot.
  • Find Minimum in Rotated Sorted Array II (LC 154) — with duplicates.

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 does duplicates break the O(log n) bound?

When nums[lo] == nums[mid] == nums[hi], you can't tell which side is sorted. The only safe move is to shrink by one (lo++ or hi--), which costs O(n) worst case.

Why use <= when comparing nums[lo] and nums[mid]?

Because when lo == mid (range of size 1 or 2), the single element on the left is trivially 'sorted' — equal counts as sorted. Strict < would mis-identify the sorted half.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →