Search in Rotated Sorted Array

Problem

An ascending array of distinct integers was rotated at some unknown pivot: some suffix of the sorted array was moved to the front. For example, [0,1,2,4,5,6,7] rotated at index 3 becomes [4,5,6,7,0,1,2]. (The rotation may also be trivial — the array left as-is.)

Given the rotated array nums and a target, return the index of target in nums, or -1 if it is not present. Your algorithm must run in O(log n) time.

Examples

• nums = [4,5,6,7,0,1,2], target = 0 → 4 0 sits at index 4, in the smaller “right half” of the rotation.
• nums = [4,5,6,7,0,1,2], target = 3 → -1 3 is not in the array.
• nums = [1], target = 1 → 0 A single-element array; the rotation is trivial.

Constraints

• 1 <= len(nums) <= 5000
• -10^4 <= nums[i], target <= 10^4
• All values are distinct.
• Required time: O(log n) — the constraint that rules out a linear scan.

Think about it first

TL;DR

One-pass modified binary search (“recurse into the half that could contain the target”) — O(log n) time, O(1) space.

Approach 1 — Brute force

Ignore the structure and scan.

from typing import List


def search(nums: List[int], target: int) -> int:
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

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

With n <= 5000 this passes, but the problem explicitly requires O(log n), so the linear scan does not qualify.

Approach 2 — Find the pivot, then binary search a sorted segment

The insight: a rotated sorted array is two sorted segments, split at the minimum element (the pivot). Binary search can find the pivot: compare nums[mid] to nums[hi] — if nums[mid] > nums[hi], the minimum lies strictly to the right of mid; otherwise it is at mid or to the left. Once you know the pivot, the target lives in exactly one of the two sorted segments (decidable by comparing with nums[-1]), and a standard binary search finds it.

import bisect
from typing import List


def search(nums: List[int], target: int) -> int:
    n = len(nums)

    # Phase 1: find index of the minimum (the rotation pivot).
    lo, hi = 0, n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    pivot = lo

    # Phase 2: pick the sorted segment that could hold target.
    if pivot != 0 and nums[0] <= target <= nums[pivot - 1]:
        lo, hi = 0, pivot - 1
    else:
        lo, hi = pivot, n - 1

    i = bisect.bisect_left(nums, target, lo, hi + 1)
    return i if i <= hi and nums[i] == target else -1

Walkthrough on nums = [4,5,6,7,0,1,2], target = 0:

1. Pivot search: (lo,hi) = (0,6), mid = 3, 7 > 2 → lo = 4. Then mid = 5, 1 <= 2 → hi = 5. Then mid = 4, 0 <= 1 → hi = 4. Loop ends: pivot = 4.
2. Segment choice: nums[0] = 4 > 0, so target can’t be in [4,5,6,7]; search nums[4..6] = [0,1,2].
3. bisect_left returns 4, and nums[4] == 0 → answer 4.

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

Approach 3 — One-pass modified binary search

The insight: you don’t need to know the pivot in advance. Wherever you cut a rotated array, at least one half is fully sorted (if nums[lo] <= nums[mid], the left half is; otherwise the right half is). A sorted half admits an O(1) range check: the target is inside it iff its value lies between the half’s endpoints. Keep the half that could contain the target and discard the other.

Each iteration makes one of these decisions:

flowchart TD
  A["mid = (lo + hi) / 2"] --> B{"nums[mid] == target?"}
  B -->|yes| C["return mid"]
  B -->|no| D{"nums[lo] <= nums[mid]?"}
  D -->|left half sorted| E{"nums[lo] <= target < nums[mid]?"}
  E -->|yes| F["hi = mid - 1"]
  E -->|no| G["lo = mid + 1"]
  D -->|right half sorted| H{"nums[mid] < target <= nums[hi]?"}
  H -->|yes| I["lo = mid + 1"]
  H -->|no| J["hi = mid - 1"]

from typing import List


def search(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 sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                               # right half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Walkthrough on nums = [4,5,6,7,0,1,2], target = 0:

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

Both approaches are O(log n); the one-pass version is the standard interview answer, while the pivot-first version decomposes into two vanilla binary searches and is easier to verify piece by piece.

Common pitfalls

• Using strict < in the sorted-half test: it must be nums[lo] <= nums[mid] so a one-element half (lo == mid) counts as sorted.
• Getting the range checks half-open wrong — nums[lo] <= target < nums[mid] and nums[mid] < target <= nums[hi]; mid itself is already excluded by the equality check.
• Assuming this exact code handles duplicates — it doesn’t. With duplicates (Search in Rotated Sorted Array II), nums[lo] == nums[mid] == nums[hi] is ambiguous and forces shrinking the bounds by one, degrading the worst case to O(n).
• Comparing against nums[mid]’s index position instead of the endpoint values when deciding which half to keep.

Pattern takeaway

Binary search still works when global order is broken, as long as each split leaves one half you can reason about in O(1). A rotated sorted array guarantees that: one half is always sorted, and a sorted range answers “could the target be here?” directly. When an array is almost sorted, look for the invariant each half still satisfies before giving up on O(log n).