LeetCode 33: Search In Rotated Sorted Array — Step-by-Step Visual Trace

#python #leetcode #algorithms

Medium — Binary Search | Array | Divide and Conquer

The Problem

Find the index of a target value in a rotated sorted array, where a sorted array has been rotated at some pivot point. Return -1 if the target is not found.

Approach

Use modified binary search by determining which half of the array is properly sorted at each step. Compare the target with the sorted half's bounds to decide whether to search left or right. This maintains O(log n) complexity despite the rotation.

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

Code

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 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