Mid-levelMid (3–6 yrs)CodingPythonAmazonMetaLinkedIn

Search in Rotated Sorted Array

A sorted array was rotated at an unknown pivot. Return the index of target in O(log n), or -1.

Answers use simple, clear English.

Time: O(log n)Space: O(1)

Quick interview answer

Modified binary search: check which half is sorted using nums[lo] vs nums[mid]. If target lies in the sorted half, search there; else search the other half.

Detailed answer

Modified binary search: check which half is sorted using nums[lo] vs nums[mid]. If target lies in the sorted half, search there; else search the other half. Duplicates (LC 81) need careful equality handling and can degrade to O(n).

Full explanation

Duplicates (LC 81) need careful equality handling and can degrade to O(n).

Real example & use case

Circular buffer of sensor readings stored rotated; find a timestamp quickly.

Pros & cons

Pros: keeps log n. Cons: branchy invariants; duplicates complicate.

Code example

def search(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]:
            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

Practice code · python (view only · no execution)

def search(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]:
            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

#binary-search#rotated