Skip to main content

41. Search in Rotated Sorted Array

mediumAsked at Vercel

Search for a target in a rotated sorted array in O(log n). Vercel asks this for the binary-search-with-rotation reasoning — same shape as their consistent-hashing key lookup when the ring has been shifted.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; modified binary search expected.
  • Blind (2026-Q1)— Listed in Vercel routing engineer screen.

Problem

There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed, 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

Approaches

1. Linear scan

Walk the array; return index of target or -1.

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

Tradeoff: Violates O(log n). Mention only to set the bar.

2. Modified binary search (optimal)

Standard binary search but at each mid, decide which half is sorted (left or right). Target either lies in the sorted half (narrow toward it) or in the unsorted half (search there).

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

Tradeoff: O(log n). The key insight: at any mid, at least one half is sorted. Check if target is within that sorted half's range — if so, narrow there; otherwise narrow the other half.

Vercel-specific tips

Vercel grades for the 'which half is sorted' reasoning. Bonus signal: drawing the rotated array and labeling which half is sorted at a hypothetical mid before writing code. The `<=` comparisons matter for the no-rotation edge case.

Common mistakes

  • Using `<` instead of `<=` in `nums[lo] <= nums[mid]` — fails when lo == mid (single-element half).
  • Confusing 'sorted half contains target' check — must use the bounds of THAT half, not the whole range.
  • Forgetting that rotation might be 0 — should still work with the same code.

Follow-up questions

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

  • Search in Rotated Sorted Array II (LC 81) — duplicates allowed.
  • Find Minimum in Rotated Sorted Array (LC 153).
  • Two-step approach: find rotation index, then binary search.

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 one half have to be sorted?

The array is rotated at most once. At any mid, at least one of [lo, mid] or [mid, hi] is contiguous (un-rotated) — therefore sorted. The other half contains the rotation pivot.

Why `nums[lo] <= nums[mid]` and not `<`?

When lo == mid (single-element half), the half is trivially sorted. `<=` covers that; `<` would put us in the wrong branch.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →