LeetCode Search in Rotated Sorted Array

Intermediate 8 min read

What you'll learn

✓How rotation breaks plain binary search and how to fix it
✓How to decide which half is sorted at each step
✓A clean iterative O(log n) implementation
✓Edge cases around duplicates and small arrays
✓How to walk an interviewer through the invariant

Prerequisites

•Basic [binary search](/blog/searching-binary-search)
•Comfort with [arrays](/blog/arrays-introduction)

Search in Rotated Sorted Array (LeetCode 33, Medium) is the interview classic that proves you actually understand binary search rather than memorized it. The array is sorted, then rotated; you must find a target in O(log n).

The Problem

Given an integer array nums sorted in ascending order, possibly rotated at an unknown pivot, and an integer target, return the index of target or -1. All values are distinct.

Example:

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

Brute Force

Linear scan.

def search_brute(nums, target):
    for i, x in enumerate(nums):
        if x == target:
            return i
    return -1

O(n). Works but ignores the structure.

Optimal Solution

At every midpoint, at least one of [low..mid] or [mid..high] is sorted. Check which, then decide whether the target lies in that sorted half.

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

O(log n) time, O(1) space.

Walk Through an Example

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

lo=0, hi=6, mid=3, nums[mid]=7. Left half [4,5,6,7] is sorted because 4 <= 7. Is target in [4,7)? No. So lo = 4.
lo=4, hi=6, mid=5, nums[mid]=1. Left half [0,1] sorted, 0 <= 1. Is target in [0,1)? Yes. So hi = 4.
lo=4, hi=4, mid=4, nums[mid]=0. Match. Return 4.

Edge Cases

Single-element array: return 0 if it matches, else -1.
Array not actually rotated: degenerates to standard binary search.
Target smaller than min or larger than max: returns -1 after log steps.
Two-element arrays like [3,1]: the half-sorted check still holds.
LeetCode 81 variant allows duplicates and needs an extra shrink step when nums[lo] == nums[mid] == nums[hi].

Complexity Analysis

Brute force: O(n) time, O(1) space.
Modified binary search: O(log n) time, O(1) space.

You halve the search range every iteration, just with a smarter branch decision.

How to Explain It in an Interview

Start with the key claim: for any midpoint in a rotated sorted array of distinct values, one side is sorted. Prove it briefly: if nums[lo] <= nums[mid], the left side has no pivot in it. From there, the rule is mechanical. If the target falls in the sorted side’s value range, recurse there; otherwise the other side. Mention the duplicates variant (LeetCode 81) to show breadth, but solve the distinct version cleanly first.

LeetCode 153 Find Minimum in Rotated Sorted Array
LeetCode 81 Search in Rotated Sorted Array II (duplicates)
LeetCode 162 Find Peak Element (binary search on shape)
LeetCode 704 Binary Search (baseline)

Wrap up

Rotated array search is the litmus test for binary search intuition. The trick is reducing to “which half is sorted” and asking “does the target fit there?” Master this template and you’ll handle peak-finding, rotation pivots, and many bound-finding variants in the same breath. Pair it with the Big-O intuition for halving.