33. Search in Rotated Sorted Array (Medium)

Problem

There is an integer array nums (originally sorted in ascending order with distinct values) that has been rotated by an unknown pivot. Given the rotated array and a target, return the index of the target, or -1 if not present. Must run in $O(log n)$.

Example

• nums = [4,5,6,7,0,1,2], target = 0 → 4
• nums = [4,5,6,7,0,1,2], target = 3 → -1
• nums = [1], target = 0 → -1

LeetCode 33 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, linear scan

Python

def search(nums: list[int], target: int) -> int:
    for i, x in enumerate(nums):    # L1: scan all elements, up to n
        if x == target:             # L2: O(1) compare
            return i
    return -1

TypeScript

function search(nums: number[], target: number): number {
    for (let i = 0; i < nums.length; i++) {  // L1: scan all elements, up to n
        if (nums[i] === target) return i;     // L2: O(1) compare
    }
    return -1;
}

Go

func search(nums []int, target int) int {
    for i, x := range nums {  // L1: scan all elements, up to n
        if x == target {      // L2: O(1) compare
            return i
        }
    }
    return -1
}

Swift

final class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        nums.firstIndex(of: target) ?? -1
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1/L2 (linear scan)	$O(1)$	n	$O(n)$ ← dominates

Complexity

• Time: $O(n)$, driven by L1 (ignores the rotated-sorted structure entirely).
• Space: $O(1)$.

Violates the $O(log n)$ requirement.

Approach 2: Find pivot, then binary search in the right half

First, find the rotation index (minimum) with a binary search (Approach 3 from 153). Then binary-search the relevant half.

Python

def search(nums: list[int], target: int) -> int:
    # Step 1: find rotation pivot (index of min)
    lo, hi = 0, len(nums) - 1               # L1: O(1)
    while lo < hi:                           # L2: first binary search, O(log n)
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    pivot = lo                               # L3: O(1) pivot found
    # Step 2: pick which half to binary-search
    if pivot == 0 or target < nums[0]:
        lo, hi = pivot, len(nums) - 1       # L4: O(1) right segment
    else:
        lo, hi = 0, pivot - 1              # L5: O(1) left segment
    while lo <= hi:                          # L6: second binary search, O(log n)
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

TypeScript

function search(nums: number[], target: number): number {
    // Step 1: find rotation pivot (index of min)
    let lo = 0, hi = nums.length - 1;
    while (lo < hi) {                              // L2: first binary search, O(log n)
        const mid = (lo + hi) >> 1;
        if (nums[mid] > nums[hi]) lo = mid + 1;
        else hi = mid;
    }
    const pivot = lo;                              // L3: O(1) pivot found
    // Step 2: pick which half to binary-search
    if (pivot === 0 || target < nums[0]) {
        lo = pivot; hi = nums.length - 1;          // L4: O(1) right segment
    } else {
        lo = 0; hi = pivot - 1;                   // L5: O(1) left segment
    }
    while (lo <= hi) {                             // L6: second binary search, O(log n)
        const mid = (lo + hi) >> 1;
        if (nums[mid] === target) return mid;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Go

func search(nums []int, target int) int {
    // Step 1: find rotation pivot (index of min)
    lo, hi := 0, len(nums)-1
    for lo < hi {                              // L2: first binary search, O(log n)
        mid := (lo + hi) / 2
        if nums[mid] > nums[hi] {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    pivot := lo                                // L3: O(1) pivot found
    // Step 2: pick which half to binary-search
    if pivot == 0 || target < nums[0] {
        lo, hi = pivot, len(nums)-1           // L4: O(1) right segment
    } else {
        lo, hi = 0, pivot-1                  // L5: O(1) left segment
    }
    for lo <= hi {                             // L6: second binary search, O(log n)
        mid := (lo + hi) / 2
        if nums[mid] == target {
            return mid
        }
        if nums[mid] < target {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return -1
}

Swift

final class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        var low = 0
        var high = nums.count - 1

        while low < high {
            let middle = low + (high - low) / 2
            if nums[middle] > nums[high] {
                low = middle + 1
            } else {
                high = middle
            }
        }

        let pivot = low
        if target >= nums[pivot] && target <= nums[nums.count - 1] {
            low = pivot
            high = nums.count - 1
        } else {
            low = 0
            high = pivot - 1
        }

        while low <= high {
            let middle = low + (high - low) / 2
            if nums[middle] == target { return middle }
            if nums[middle] < target {
                low = middle + 1
            } else {
                high = middle - 1
            }
        }
        return -1
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1-L3 (find pivot)	$O(1)$ per step	log n	$O(log n)$
L4 or L5 (pick segment)	$O(1)$	1	$O(1)$
L6 (binary search segment)	$O(1)$ per step	log n	$O(log n)$ ← dominates

Two sequential $O(log n)$ binary searches on disjoint parts of the array. The total is 2 × $O(log n)$ = $O(log n)$.

Complexity

• Time: $O(log n)$, driven by L2 and L6 (two independent $O(log n)$ binary searches).
• Space: $O(1)$.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: One-pass modified binary search (optimal)

At each step, one of the halves is guaranteed to be sorted. Check which, then decide based on the target’s position relative to that sorted half.

Python

def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1             # L1: O(1)
    while lo <= hi:                        # L2: loop, O(log n) iterations
        mid = (lo + hi) // 2              # L3: O(1) midpoint
        if nums[mid] == target:            # L4: O(1) compare
            return mid
        if nums[lo] <= nums[mid]:          # L5: O(1) left-half sorted check
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1              # L6: O(1) target in left half
            else:
                lo = mid + 1              # L7: O(1) target in right half
        else:                              # right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1              # L8: O(1) target in right half
            else:
                hi = mid - 1             # L9: O(1) target in left half
    return -1

TypeScript

function search(nums: number[], target: number): number {
    let lo = 0, hi = nums.length - 1;
    while (lo <= hi) {                               // L2: loop, O(log n) iterations
        const mid = (lo + hi) >> 1;                  // L3: O(1) midpoint
        if (nums[mid] === target) return mid;         // L4: O(1) compare
        if (nums[lo] <= nums[mid]) {                 // L5: O(1) left-half sorted check
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;  // L6
            else lo = mid + 1;                       // L7
        } else {                                     // right half is sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;  // L8
            else hi = mid - 1;                       // L9
        }
    }
    return -1;
}

Go

func search(nums []int, target int) int {
    lo, hi := 0, len(nums)-1
    for lo <= hi {                               // L2: loop, O(log n) iterations
        mid := (lo + hi) / 2                   // L3: O(1) midpoint
        if nums[mid] == target {                // L4: O(1) compare
            return mid
        }
        if nums[lo] <= nums[mid] {             // L5: O(1) left-half sorted check
            if nums[lo] <= target && target < nums[mid] {
                hi = mid - 1                   // L6: O(1) target in left half
            } else {
                lo = mid + 1                   // L7: O(1) target in right half
            }
        } else {                               // right half is sorted
            if nums[mid] < target && target <= nums[hi] {
                lo = mid + 1                   // L8: O(1) target in right half
            } else {
                hi = mid - 1                  // L9: O(1) target in left half
            }
        }
    }
    return -1
}

Swift

final class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        var low = 0
        var high = nums.count - 1

        while low <= high {
            let middle = low + (high - low) / 2
            if nums[middle] == target { return middle }

            if nums[low] <= nums[middle] {
                if nums[low] <= target && target < nums[middle] {
                    high = middle - 1
                } else {
                    low = middle + 1
                }
            } else if nums[middle] < target && target <= nums[high] {
                low = middle + 1
            } else {
                high = middle - 1
            }
        }
        return -1
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (init)	$O(1)$	1	$O(1)$
L2/L3/L4/L5 (loop body)	$O(1)$	log n	$O(log n)$ ← dominates
L6/L7/L8/L9 (narrow range)	$O(1)$	log n	$O(log n)$

Each iteration either returns (found) or eliminates half the remaining range. The nums[lo] <= nums[mid] check at L5 identifies which half is a contiguous sorted run in $O(1)$.

Complexity

• Time: $O(log n)$, driven by L2/L3/L4/L5 (single pass that halves range each step).
• Space: $O(1)$.

Why it works

A rotation means the array is two sorted runs. Whatever mid you pick, one of [lo, mid] or [mid, hi] is entirely within a single run, hence sorted. The nums[lo] <= nums[mid] comparison detects which side is sorted.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift notes

Passing [Int] into these methods does not eagerly copy its storage. Every approach treats the array as read-only, so copy-on-write never needs to duplicate the buffer. Computing mid as lo + (hi - lo) / 2 also keeps the midpoint expression safe when indexes become large.

Summary

Approach	Time	Space
Linear scan	$O(n)$	$O(1)$
Find pivot + binary search	$O(log n)$	$O(1)$
One-pass modified binary search	$O(log n)$	$O(1)$

The one-pass variant is the cleanest, and extends with small adjustments to problem 81 (rotated with duplicates), where the worst case degrades to $O(n)$ because duplicates can break the “one half is sorted” guarantee.

Test cases

Python

# Quick smoke tests - paste into a REPL or save as test_033.py and run.
# Uses the optimal Approach 3 implementation.

def search(nums: list, target: int) -> int:
    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

def _run_tests():
    assert search([4, 5, 6, 7, 0, 1, 2], 0) == 4
    assert search([4, 5, 6, 7, 0, 1, 2], 3) == -1    # not present
    assert search([1], 0) == -1                        # single element miss
    assert search([1], 1) == 0                         # single element hit
    assert search([3, 1], 1) == 1                      # small rotated, target on right
    assert search([3, 1], 3) == 0                      # small rotated, target on left
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function search(nums: number[], target: number): number {
    let lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        if (nums[mid] === target) return mid;
        if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

console.assert(search([4, 5, 6, 7, 0, 1, 2], 0) === 4);
console.assert(search([4, 5, 6, 7, 0, 1, 2], 3) === -1);   // not present
console.assert(search([1], 0) === -1);                        // single element miss
console.assert(search([1], 1) === 0);                         // single element hit
console.assert(search([3, 1], 1) === 1);                      // small rotated, target on right
console.assert(search([3, 1], 3) === 0);                      // small rotated, target on left
console.log("all tests pass");

Go

package main

import "fmt"

func search(nums []int, target int) int {
    lo, hi := 0, len(nums)-1
    for lo <= hi {
        mid := (lo + hi) / 2
        if nums[mid] == target {
            return mid
        }
        if nums[lo] <= nums[mid] {
            if nums[lo] <= target && target < nums[mid] {
                hi = mid - 1
            } else {
                lo = mid + 1
            }
        } else {
            if nums[mid] < target && target <= nums[hi] {
                lo = mid + 1
            } else {
                hi = mid - 1
            }
        }
    }
    return -1
}

func main() {
    if search([]int{4, 5, 6, 7, 0, 1, 2}, 0) != 4  { panic("test 1") }
    if search([]int{4, 5, 6, 7, 0, 1, 2}, 3) != -1 { panic("test 2") } // not present
    if search([]int{1}, 0) != -1                     { panic("test 3") } // single element miss
    if search([]int{1}, 1) != 0                      { panic("test 4") } // single element hit
    if search([]int{3, 1}, 1) != 1                   { panic("test 5") } // small rotated, target on right
    if search([]int{3, 1}, 3) != 0                   { panic("test 6") } // small rotated, target on left
    fmt.Println("all tests pass")
}

Related data structures

• Arrays, rotated-sorted invariant; modified binary search

Related concepts

• Binary Search, the halving tactic for ordered spaces where one side can be discarded.
• Modified Binary Search, the binary search variant for rotated, peaked, or partly ordered data.