Skip to main content

41. Search in Rotated Sorted Array

mediumAsked at Reddit

Search for a target in a rotated sorted array in O(log n). Reddit asks this to test binary-search variants — the same skill used when their pagination cursor wraps around a sorted vote-timestamp index.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, common medium-difficulty binary search.
  • Blind (2025-11)— Reported on Reddit infra-team rounds.

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 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: Fails the explicit O(log n) requirement.

2. Modified binary search (optimal)

At each midpoint, one half is sorted. Check if target lies in the sorted half; recurse 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 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 key insight: at least one half is always sorted.

Reddit-specific tips

Reddit interviewers grade on the 'one half is always sorted' insight. Bonus signal: state the invariant explicitly before coding. Mention that LC 81 adds duplicates (which break the O(log n) guarantee — degrades to O(n)).

Common mistakes

  • Using strict < where <= is needed (nums[lo] <= nums[mid] handles the case when lo == mid).
  • Misidentifying which half is sorted (always compare nums[lo] with nums[mid]).
  • Off-by-one in target range check (use < or <= correctly based on which boundary equals what).

Follow-up questions

An interviewer at Reddit 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).
  • 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 at least one half always sorted?

A rotated sorted array has one pivot. If the pivot isn't in [lo, mid], the left half is sorted; otherwise the right is.

Why O(n) for duplicates (LC 81)?

If nums[lo] == nums[mid] == nums[hi], you can't tell which half is sorted; must shrink both ends.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →