Skip to main content

33. Search in Rotated Sorted Array

mediumAsked at Google

Search for a target in a sorted array that has been rotated at some unknown pivot. Google asks this to test whether you can apply modified binary search and 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 Google loops.

  • Glassdoor (2026-Q1)— Google L3/L4 onsite reports cite this as a 30-minute medium.
  • Reddit r/cscareerquestions (2025-11)— Recurring Google new-grad onsite question.

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.
  • -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 where nums[i] === 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: Violates the O(log n) requirement — mention only to anchor the comparison.

2. Modified binary search (optimal)

At each step, one half [lo..mid] or [mid..hi] is guaranteed sorted. Check which half is sorted, then decide if target lies in that 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: True O(log n) by leveraging the invariant that at least one half is always sorted in a rotated array. Edge case: nums[lo] <= nums[mid] uses <= to handle lo == mid.

Google-specific tips

Google interviewers want you to articulate the invariant: 'In a rotated sorted array, at least one half from a chosen midpoint is guaranteed to be sorted.' Walk through how you decide which half, then how you check if target lies in the sorted half. Skipping that articulation costs communication points.

Common mistakes

  • Using < instead of <= when comparing nums[lo] and nums[mid] — fails when lo === mid.
  • Forgetting that target must be strictly less than nums[mid] (not <=) when searching the left half — otherwise you re-test nums[mid].
  • Trying to find the pivot first, then binary-searching — works but is more code and more edge cases.

Follow-up questions

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

  • What if duplicates are allowed? (LC 81 — degrades to O(n) worst case.)
  • Find the minimum in a rotated sorted array (LC 153).
  • Find the rotation index without searching for a target.

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 the invariant 'one half is always sorted' hold?

A rotated sorted array has at most one 'break point'. Any midpoint divides the array into two halves; the break point can be in at most one of them, so the other is fully sorted.

Can I find the pivot first?

Yes — two binary searches (find pivot, then search the correct half). Same O(log n) complexity but more code and more edge cases. Modified binary search in one pass is cleaner.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →