Search in Rotated Sorted Array: One Half Is Always Sorted

"Search in Rotated Sorted Array" is a Medium-level staple in Meta, Amazon, Microsoft loops, and it is a textbook fit for the Modified Binary Search pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 4 of 11 in the Modified Binary Search arc.

The Problem

A sorted array of distinct values was rotated at an unknown pivot. Given the rotated array and a target, return its index or -1 in O(log n). Perennially in the top handful of most-asked questions across FAANG — a rite of passage for the pattern.

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

Recognizing the Modified Binary Search Pattern

Binary search is not about sorted arrays — it is about any monotonic predicate: if the answer space splits into a false-region followed by a true-region, you can halve it. FAANG interviews rarely ask the textbook version; they ask rotated arrays, boundary-finding, and search-on-the-answer problems where the array being searched is conceptual. Getting the loop invariant right is the whole game.

Rotation breaks global sortedness but preserves a powerful local fact: at any midpoint, at least one half is fully sorted — the half without the rotation seam. A sorted half supports an O(1) range check, which restores the ability to discard half the array.

The Approach

Compare nums[lo] with nums[mid] to identify the sorted half. If the target's value lies inside the sorted half's range, recurse into it; otherwise the target — if present — must be in the other half. Either way, half the array is eliminated per step.

The comparison nums[lo] <= nums[mid] with equality matters for two-element ranges where lo equals mid — the planted off-by-one. Dry-run [3, 1] with target 1 before calling it done.

Python Solution

def search_rotated(nums: list[int], target: int) -> int:
    """Index of target in a rotated sorted array of distinct values."""
    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

Complexity

• Time: O(log n) — one half is discarded per iteration
• Space: O(1) — iterative, constant state

Interview Tips and Follow-Ups

• With duplicates (Rotated II), nums[lo] == nums[mid] becomes ambiguous — shrink lo by one and accept O(n) worst case. Know why the guarantee degrades.
• The two-pass alternative (find pivot via Find Minimum, then plain search in the right segment) is equally valid — offering both shows depth.
• Chained range checks like nums[lo] <= target < nums[mid] are idiomatic Python — use them; they eliminate a whole class of paren bugs.

That wraps part 4 of the Modified Binary Search arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.