Skip to main content

33. Search in Rotated Sorted Array

medium

Find a target in a sorted array that's been rotated at an unknown pivot. The canonical 'one half is always sorted' trick — a top-five most asked binary search variation at FAANG.

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

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) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. 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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Key invariant: for any midpoint, at least one of [lo..mid] and [mid..hi] is strictly sorted.

Hint 2

Decide which half is sorted by comparing nums[lo] to nums[mid].

Hint 3

If the sorted half contains target (bounded between its endpoints), search there. Otherwise search the other half.

Hint 4

Standard lo/hi/mid bookkeeping — just choose direction based on the sorted-half test instead of a single comparison.

Solution approach

Reveal approach

Modified binary search. Loop while lo <= hi: mid = lo + (hi - lo) / 2. If nums[mid] == target, return mid. Determine which half is sorted: if nums[lo] <= nums[mid], the left half [lo..mid] is sorted; check if target is in that range (nums[lo] <= target < nums[mid]) — if yes search left (hi = mid - 1), else search right (lo = mid + 1). Otherwise the right half [mid..hi] is sorted; if nums[mid] < target <= nums[hi], search right, else search left. Return -1 if the loop exits without finding target. O(log n) time, O(1) space. The clean version: at each step exactly one half is sorted, and you can decide in O(1) whether target lies in it.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • binary-search

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft
  • LinkedIn
  • Apple

Practice these live with InterviewChamp.AI

Drill Search in Rotated Sorted Array and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →