Search in Rotated Sorted Array

An array of distinct integers was sorted in increasing order and then possibly rotated: some number of elements were moved, in order, from the front to the back. For example, [1, 3, 4, 6, 7, 9] rotated by three becomes [6, 7, 9, 1, 3, 4]. The rotation may also be zero, leaving the array fully sorted.

Given this array nums and an integer target, return the index of target in nums, or -1 if it is not there.

Your algorithm must run in O(log n) time.

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 5000
• -104 <= nums[i], target <= 104
• All values in nums are distinct.
• nums is an ascending array rotated by some amount between 0 and n - 1.

Pattern Path · Binary Search · problem 59 of 169

Start simple

Scan every element until you find the target: O(n) time, O(1) space.

The key idea

Ordinary binary search works because one comparison tells you which half can still contain the target. A rotated array breaks that for the array as a whole, but not for its halves: when you split [lo, hi] at mid, the rotation point (the place where values drop) can be in at most one half, so the other half is plain sorted.

If nums[lo] <= nums[mid], the left half [lo, mid] is sorted. Because it is sorted, you can check exactly whether target falls in [nums[lo], nums[mid]). If it does, continue in the left half; otherwise the target can only be on the right. Symmetrically, if the left half is not sorted then the right half [mid, hi] is, and you test target against (nums[mid], nums[hi]].

Every step discards half of the range, just like normal binary search, giving O(log n). Distinct values guarantee the nums[lo] <= nums[mid] test is never ambiguous.

Complexity

• Time: O(log n)
• Space: O(1)

Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[lo] <= nums[mid]:
                # Left half [lo, mid] is sorted.
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                # Right half [mid, hi] is sorted.
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return -1

JavaScript

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

What the interviewer is checking

It tests whether you understand why binary search works (an invariant that lets you drop half the range) rather than just memorising the template.

Mistakes to avoid

• Using < instead of <= in nums[lo] <= nums[mid], which fails when lo == mid (two-element ranges).
• Getting the range checks' strict and non-strict bounds wrong, so the target sitting exactly at lo or hi is skipped.
• Finding the rotation point first and then searching works, but it is easy to get off-by-one errors in the index mapping.

Follow-ups to expect

• What if the array may contain duplicates? (Worst case O(n); shrink both ends.)
• How do you find the minimum element? (Binary search for the drop.)
• How many times was the array rotated? (Index of the minimum.)

In real software

Circular buffers and log files that wrap around keep data sorted but rotated; finding a timestamp in such a ring buffer uses exactly this search.

Practice next