Search in Rotated Sorted Array

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    A sorted array of distinct integers has been rotated at some unknown position (for example [0, 1, 2, 4, 5, 6, 7] became [4, 5, 6, 7, 0, 1, 2]). Given the rotated array and a target, return the target's index, or −1 if it isn't there, in O(log n) time.

    The O(log n) requirement rules out a scan. The trick is that even a rotated array still has a sorted half on one side of any midpoint, and that's enough to keep binary search working. Original problem: LeetCode 33.

    Example

    The array 4,5,6,7,0,1,2 is a sorted list rotated at index 4; target 0 is at index 4, and 3 is absent.
    The array 4,5,6,7,0,1,2 is a sorted list rotated at index 4; target 0 is at index 4, and 3 is absent.
    Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 0
    Output: 4
    Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 3
    Output: -1

    Constraints (assumed)

    • 1 ≤ n ≤ 5,000 (the method works for any n).
    • All values distinct; −10⁴ ≤ value ≤ 10⁴.

    What this question tests

    • Adapting binary search to an array that is only piecewise sorted.
    • Finding an invariant that holds at every step (one half is sorted).
    • Getting the boundary conditions (≤ vs <) right.

    Questions to ask first

    1. Are values distinct? (Here: yes. With duplicates, the worst case becomes O(n); see Variants.)
    2. Could the array not be rotated at all? (Yes; the same code handles it.)
    3. Return any index or the first? With distinct values there's only one.
    4. Is O(n) acceptable? (No; the point is O(log n).)