Search in Rotated Sorted Array

Solving tips

Key insight: no matter where you cut a rotated sorted array, at least one half is fully sorted; detect which by comparing nums[lo] with nums[mid] (use <= so a one-element half counts as sorted).
For the sorted half do an O(1) range check on the target's value; if it lies inside, recurse there, otherwise recurse into the other half, standard binary search invariant.
Target O(log n) time, O(1) space; get the half-open ranges right (nums[lo] <= target < nums[mid], nums[mid] < target <= nums[hi]) since mid is excluded by the equality check.
Pitfall: this exact code assumes distinct values, duplicates (Search in Rotated Sorted Array II) make nums[lo]==nums[mid]==nums[hi] ambiguous and degrade to O(n).

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

Hint 1

Cut the rotated array anywhere. Can both halves be unsorted at the same time?

Hint 2

At least one half of any split is perfectly sorted, and you can tell which by comparing `nums[lo]` with `nums[mid]`. For a sorted half you can check in O(1) whether the target's value could be inside it.

Hint 3

Standard binary search, with one twist per iteration: identify the sorted half; if the target lies within that half's value range, recurse into it, otherwise recurse into the other half. (Alternatively: first binary-search for the pivot — the minimum — then run a normal binary search in whichever of the two sorted segments could contain the target.)

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


class Solution:
    def search(self, 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 in practice, but the problem explicitly requires O(log n) — the linear scan throws away the near-sortedness that makes the problem interesting.

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 textbook binary search finishes the job.

Binary search is the classical O(log n) technique of halving a search interval using one comparison per step.

import bisect
from typing import List


class Solution:
    def search(self, 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:

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.
Segment choice: nums[0] = 4 > 0, so target can’t be in [4,5,6,7]; search nums[4..6] = [0,1,2].
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, discard the other — classic binary search invariant, with the “which half” test upgraded.

from typing import List


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 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:

lo	hi	mid	nums[mid]	sorted half	target in it?	action
0	6	3	7	left `[4..7]`	4 <= 0 < 7? no	lo = 4
4	6	5	1	left `[0..1]`	0 <= 0 < 1? yes	hi = 4
4	4	4	0	—	match	return 4

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 survives broken global order as long as every split leaves you one half you can reason about in O(1). “Rotated sorted” grants exactly that: one half is always sorted, and a sorted range answers “could the target be here?” instantly. When an array is almost sorted, ask what invariant each half still satisfies before giving up on O(log n).