Skip to main content

33. Search in Rotated Sorted Array

mediumAsked at Netflix

Search a target in an array that was sorted ascending then rotated at an unknown pivot. Netflix asks this on the binary-search round — they want a single-pass O(log n) solution where you reason about which half is sorted at each step.

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

Source citations

Public interview reports confirming this problem appears in Netflix loops.

  • Glassdoor (2026-Q1)— Netflix SWE phone-screen reports list this as the canonical binary-search question.
  • Blind (2025-11)— Netflix L4 interview write-ups describe the 'which half is sorted' narration as the explicit signal.

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

Example 3

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

Approaches

1. Linear scan

Walk the array; return the first index whose value equals target.

Time
O(n)
Space
O(1)
function searchLinear(nums, target) {
  for (let i = 0; i < nums.length; i++) if (nums[i] === target) return i;
  return -1;
}

Tradeoff: Correct but doesn't meet the stated O(log n) requirement — it's only useful as a sanity baseline.

2. Modified binary search (optimal)

At each midpoint, decide whether the left half [l..mid] or right half [mid..r] is sorted. Then check whether target lies in the sorted half; if yes, recurse there; otherwise the other half.

Time
O(log n)
Space
O(1)
function search(nums, target) {
  let l = 0, r = nums.length - 1;
  while (l <= r) {
    const mid = (l + r) >> 1;
    if (nums[mid] === target) return mid;
    if (nums[l] <= nums[mid]) {
      if (nums[l] <= target && target < nums[mid]) r = mid - 1;
      else l = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[r]) l = mid + 1;
      else r = mid - 1;
    }
  }
  return -1;
}

Tradeoff: Single pass, O(log n). The key insight: at any midpoint, at least one of the two halves is fully sorted. Compare nums[l] to nums[mid] to know which.

Netflix-specific tips

Netflix interviewers grade two things here: (1) Do you ALWAYS know which half is sorted? Say out loud: 'nums[l] <= nums[mid] means the left half is sorted; otherwise the right half is.' (2) Do you check the target range using inclusive vs exclusive bounds correctly? The `<=` vs `<` choices matter — get them wrong by one and you'll skip the target.

Common mistakes

  • Finding the pivot first with a separate binary search, then doing a standard search — works but doubles the constant.
  • Confusing the boundary checks: nums[l] <= target && target < nums[mid] (the left-sorted case) — the `<` at nums[mid] is correct because we already returned if nums[mid] === target.
  • Using nums[l] < nums[mid] instead of <= — fails when l === mid.

Follow-up questions

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

  • Search in Rotated Sorted Array II (LC 81) — what if duplicates are allowed? (Worst-case O(n) when nums[l] === nums[mid] === nums[r].)
  • Find Minimum in Rotated Sorted Array (LC 153) — the pivot-finding variant.
  • What if the array were rotated multiple times? (Rotating a sorted array is idempotent — same problem.)

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 one half always sorted?

Because the array was sorted before being rotated once. The rotation puts a single 'cliff' (the pivot) somewhere. Any midpoint either has the pivot to its left or to its right; whichever side doesn't contain the pivot is still ascending.

What if the input has duplicates?

Worst case becomes O(n) because nums[l] === nums[mid] === nums[r] tells you nothing about which side is sorted. You shrink the window one element at a time in that case (LC 81).

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →