Skip to main content

41. Search in Rotated Sorted Array

mediumAsked at Snowflake

Search for a target in a sorted array that has been rotated at an unknown pivot. Snowflake asks this to test modified binary search reasoning — the same instinct used when indexing data that may be partially ordered due to micro-partition layout.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2026-Q1)— Snowflake storage team uses this to set up partial-ordering follow-up.
  • LeetCode Discuss (2025-12)— Recurring at Snowflake SDE-I onsites.

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 index when found.

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

Tradeoff: Violates the O(log n) constraint.

2. Modified binary search (optimal)

At each step, one of [lo, mid] or [mid, hi] is sorted. Decide which, then check whether target lies in that sorted half.

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: Log n. The key insight: a rotated array always has at least one sorted half — find it, check if target is in it, recurse on that half.

Snowflake-specific tips

Snowflake interviewers grade this on whether you articulate the 'one half is always sorted' invariant before coding. Bonus signal: discuss what happens with duplicates (LC 81) — the invariant weakens and worst case degrades to O(n).

Common mistakes

  • Using strict < at the wrong boundary, missing the rotation pivot.
  • Trying to first find the pivot via binary search, then doing a regular search — works but is two passes; the inline version is one pass.
  • Confusing 'left half sorted' with 'right half sorted' when nums[lo] == nums[mid].

Follow-up questions

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

  • Search in Rotated Sorted Array II (LC 81) — with duplicates.
  • Find Minimum in Rotated Sorted Array (LC 153).
  • Find Peak Element (LC 162).

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?

Rotating a sorted array at one pivot means at most one 'wrap' point. Any contiguous half that doesn't span the wrap is sorted. The mid pointer always splits such that at least one side avoids the wrap.

How would duplicates change this?

If nums[lo] == nums[mid] you can't tell which half is sorted. You'd have to inch lo forward (lo++) — worst case O(n).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →