Skip to content

061 — Search in Rotated Sorted Array

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

61 — Search in Rotated Sorted Array

LeetCode 33 · Medium. There is an integer array nums sorted in ascending order with distinct values. Before being passed to your function, nums is rotated at an unknown pivot index k (1 <= k < nums.length), so it becomes [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]. Given the rotated array and an integer target, return the index of target if it exists, or -1 otherwise, in O(log n) time.

🍽️ Intuition

A rotated sorted array looks broken — there's a jump downward somewhere in the middle — but it's really just two sorted runs glued end to end, like a deck of cards cut once and stacked back together out of order. The trick is that at any midpoint you check, even though the whole array isn't sorted, at least one of the two halves around that midpoint always is. If you can tell which half is the sorted one (a single comparison against the endpoints tells you), you can also tell whether target could possibly live in that sorted half — and if it can't, you know for certain it must be in the other half, sorted or not. That's still "eliminate half the search space every step," just with an extra comparison to figure out which half to trust.

🚩 Pattern-Recognition Cue

"A rotated sorted array" combined with a required O(log n) is the direct tell — a plain linear scan trivially solves this in O(n), so the constraint alone signals that the intended solution modifies binary search rather than abandoning it. The deeper cue: even after rotation, comparing nums[lo] to nums[mid] always reveals which of the two halves is contiguous and sorted, which is enough monotonic structure for Binary Search to still apply.

🐢 Brute Force

Scan every element.

func searchBruteForce(_ nums: [Int], _ target: Int) -> Int {
    for (index, value) in nums.enumerated() {
        if value == target {
            return index
        }
    }
    return -1
}

// smoke test
print(searchBruteForce([4, 5, 6, 7, 0, 1, 2], 0))   // 4
print(searchBruteForce([4, 5, 6, 7, 0, 1, 2], 3))   // -1

Big-O: O(n) time, O(1) space.

🚀 Optimal

At each midpoint, determine which half ([lo...mid] or [mid...hi]) is properly sorted by comparing its endpoints, then check whether target falls in that sorted half's range to decide which side to keep.

func search(_ nums: [Int], _ target: Int) -> Int {
    var lo = 0
    var hi = nums.count - 1

    while lo <= hi {
        let mid = lo + (hi - lo) / 2

        if nums[mid] == target {
            return mid
        }

        if nums[lo] <= nums[mid] {
            // left half [lo...mid] is properly sorted
            if nums[lo] <= target && target < nums[mid] {
                hi = mid - 1
            } else {
                lo = mid + 1
            }
        } else {
            // right half [mid...hi] is properly sorted
            if nums[mid] < target && target <= nums[hi] {
                lo = mid + 1
            } else {
                hi = mid - 1
            }
        }
    }

    return -1
}

// smoke test
print(search([4, 5, 6, 7, 0, 1, 2], 0))   // 4
print(search([4, 5, 6, 7, 0, 1, 2], 3))   // -1
print(search([1], 0))                      // -1
print(search([5, 1, 3], 5))                // 0

Big-O: O(log n) time — one comparison per step still eliminates half the array, rotation or not. O(1) space.

🔑 The Key Insight

Rotation destroys global sortedness but not local sortedness: cutting a sorted array at one point and swapping the two pieces always leaves at least one of the two halves around any midpoint fully sorted. Comparing nums[lo] to nums[mid] costs one extra comparison but tells you which half that is — and once you know a half is sorted, a plain range check (nums[lo] <= target < nums[mid]) tells you whether target could be hiding there. If it can't be in the sorted half, it's forced into the other half by elimination, sorted or not. That one extra comparison per step is the entire adaptation; the halving logic underneath is unchanged from plain Binary Search.

🔗 Related Chapters

  • Binary Search — the pattern chapter calls out rotated arrays explicitly as still solvable because "at least one half of any subrange remains properly sorted," which is exactly the property this problem exploits.
  • Arrays & Strings — the underlying array and the O(1) indexing the algorithm depends on.
  • Find Minimum in Rotated Sorted Array — the closely related problem of locating the rotation pivot itself using the same sorted-half comparison idea.

🧸 Memory Sentence

A rotated sorted array is a deck of cards cut once and stacked back together — at every midpoint, one half is still in order, and that's the half you check to decide where the target must be.

✅ Check Your Understanding

For nums = [4, 5, 6, 7, 0, 1, 2], target = 6, trace lo, hi, mid at each step, noting at each step which half the algorithm determines is sorted and why. What would go wrong at the very first comparison if the array contained duplicate values (e.g. [3, 1, 2, 3, 3, 3, 3])?

⬅️ Previous: Koko Eating Bananas · Next: Find Minimum in Rotated Sorted Array ➡️

Clone this wiki locally