Problem 16 · Binary Search

Search in Rotated Sorted Array

MediumClassic DSA & systems

01Problem

Given a rotated sorted array of distinct integers and a target, return its index or -1 in O(log n).

02Key insight

At every midpoint at least one half is sorted; check if the target lies within that sorted half's range and discard the other half.

03Solution

solution.pypython17 lines

def search_rotated(nums: list[int], 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]:  # 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

Try it first.

TimeO(log n)

SpaceO(1)

tests.py · 4 passing

tests.pypython4 lines

assert search_rotated([4,5,6,7,0,1,2], 0) == 4
assert search_rotated([4,5,6,7,0,1,2], 3) == -1
assert search_rotated([1], 1) == 0
assert search_rotated([], 5) == -1

04Staff-level follow-up

What if duplicates are allowed? When nums[lo]==nums[mid]==nums[hi] you can't tell which half is sorted, so shrink both ends by one; worst case degrades to O(n).