roadmap/binary-search/Search in Rotated Sorted Array

Search in Rotated Sorted Array

MediumAmazonGoogleMicrosoftMetaApple

Problem

Given a rotated sorted array and a target, return the index of target or -1. Must run in O(log n).

Intuition — the key insight

Even in a rotated array, one half is always sorted. Check which half is sorted, then determine if target falls in that half. Eliminate the other half.

Approach

Modified binary search

If nums[lo]<=nums[mid], left half is sorted. If target in [nums[lo],nums[mid]), go left. Else go right. Mirror for right half sorted.

Complexity

Time

O(log n)

Space

O(1)

Standard binary search — halves search space each iteration.

Solution code

Python

def search(self, 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 sorted
            if nums[lo] <= target < nums[mid]: hi = mid-1
            else: lo = mid+1
        else:                      # right sorted
            if nums[mid] < target <= nums[hi]: lo = mid+1
            else: hi = mid-1
    return -1

Edge cases to remember

⚠No rotation: works as normal binary search

⚠Target not present: return -1

⚠Duplicates: this solution assumes no duplicates

Hints

What pattern do you think this problem uses?