Search In Rotated Sorted Array

Just walk the array looking for the target. It works regardless of rotation, but it throws away the fact that the array is built from two sorted runs, which is what the O(log n) requirement is pushing you toward.

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        for i, num in enumerate(nums):
            if num == target:
                return i
        return -1

A rotated sorted array always splits at mid into one half that is genuinely sorted and one half that still contains the rotation point. Figure out which half is sorted by comparing nums[lo] to nums[mid]. Then check whether target falls inside that sorted half’s range — if it does, recurse into it as usual; if it does not, the target (if it exists at all) must be in the other, still-rotated half.

class Solution:
    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 half [lo, mid] is sorted
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                # right half [mid, hi] is sorted
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return -1

Tracing nums = [4,5,6,7,0,1,2], target = 0:

Why it’s correct: whichever half is sorted, its endpoints give a valid range to test membership in O(1); if the target is not in that range it cannot be in that half (since that half is fully sorted and bounded), so the other half is safe to search next — no candidate index is ever discarded incorrectly. Complexity: the search window halves every iteration, giving O(log n) time, O(1) space.