Search in Rotated Sorted Array

Signal

Same rotated-but-sorted shape as finding the minimum, one level further: once you know one of the two halves around mid is properly sorted, you can check whether the target falls inside that half's range and decide which way to go — no need to actually locate the rotation point first.

Approach

At each step, figure out which half is sorted by comparing nums[left] to nums[mid]. If the left half is sorted, check whether target lies within [nums[left], nums[mid]); if so, search left, otherwise search right. Mirror the logic if the right half is the sorted one instead.

Skeleton

left, right = 0, len(nums) - 1
while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target: return mid
    if nums[left] <= nums[mid]:            # left half sorted
        if nums[left] <= target < nums[mid]: right = mid - 1
        else: left = mid + 1
    else:                                   # right half sorted
        if nums[mid] < target <= nums[right]: left = mid + 1
        else: right = mid - 1
return -1

Solution

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Complexity

O(log n) time — still one binary search, just with an extra O(1) branch per step to determine which half is sorted. O(1) space.

Pitfalls

• Using <= vs < incorrectly in the range checks silently drops the boundary elements — walk through a small rotated example by hand before trusting the inequalities.
• Trying to first find the rotation index and then binary search within the correct half is a valid two-pass approach, but doubles the code for no benefit — the single-pass version above handles both halves in one loop.
• If duplicates are allowed (LeetCode's follow-up variant), nums[left] == nums[mid] == nums[right] breaks the "which half is sorted" test entirely, forcing a fallback linear shrink (left += 1; right -= 1) in the worst case.