Search in Rotated Sorted Array

The problem

A sorted array has been rotated by some unknown pivot (e.g., [0,1,2,4,5,6,7] rotated becomes [4,5,6,7,0,1,2]). All elements are distinct. Find a given target in O(log n), or return −1.

Pattern: modified binary search

The classical binary-search invariant ("the answer, if any, lies in [lo, hi]") still holds — but the array isn't globally sorted. The key observation: at any midpoint, at least one half is fully sorted. Look at nums[lo] and nums[mid]: if nums[lo] ≤ nums[mid], the left half is sorted; otherwise the right half is. From there, decide by a simple range check whether the target lies in the sorted half or the other one.

This is one of the most common "twist on binary search" interview questions. The trick to remember is not the rotation logic itself, but the meta-pattern: preserve a clean invariant on a half, even when the global structure is broken.

Solution

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

        # Exactly one half [lo..mid] or [mid..hi] is sorted.
        if nums[lo] <= nums[mid]:
            # Left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # Right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Trace

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

lo=0, hi=6, mid=3 -> nums[mid]=7. 7 != 0.
  nums[0]=4 <= nums[3]=7, left half is sorted.
  Is 4 <= 0 < 7? No.  Search right.  lo = 4.

lo=4, hi=6, mid=5 -> nums[mid]=1. 1 != 0.
  nums[4]=0 <= nums[5]=1, left half is sorted.
  Is 0 <= 0 < 1? Yes. Search left. hi = 4.

lo=4, hi=4, mid=4 -> nums[mid]=0. Hit! return 4.

Reference: linear scan

def search_linear(nums: list[int], target: int) -> int:
    for i, x in enumerate(nums):
        if x == target: return i
    return -1

Complexity

• Time: O(log n). Same as plain binary search.
• Space: O(1).

Variations worth knowing

• With duplicates: the nums[lo] ≤ nums[mid] test becomes ambiguous when they're equal. Fall back to lo += 1 in that case — worst case O(n), but typically still fast.
• Find the rotation pivot (minimum): binary search for the index where nums[i] > nums[i+1]. The minimum is at i+1.
• Search in two dimensions (sorted matrix): if each row and each column is sorted, start at the top-right corner and walk down/left in O(n + m). Or binary search on the flattened representation if rows concatenate.
• Peak finding: in an array where neighbors differ, binary-search by comparing nums[mid] to nums[mid+1] and walking uphill. Same "invariant-preservation under irregular shape" idea.