Q48: Search in Rotated Sorted Array. - DSA Patterns (Multi-Lang)

In Simple Words: At least one half is always normally sorted:

If nums[l] <= nums[mid] (left half sorted): check if target lies between nums[l] and nums[mid].
Else (right half sorted): check if target lies between nums[mid] and nums[r].

Time: $O(\log N)$ | Space: $O(1)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def search(nums: list[int], target: int) -> int:
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = l + (r - l) // 2
        if nums[mid] == target:
            return mid
        # Left half sorted
        if nums[l] <= nums[mid]:
            if nums[l] <= target < nums[mid]:
                r = mid - 1
            else:
                l = mid + 1
        # Right half sorted
        else:
            if nums[mid] < target <= nums[r]:
                l = mid + 1
            else:
                r = mid - 1
    return -1