leetcode-33 Search in Rotated Sorted Array

[33] Search in Rotated Sorted Array

Key Concept: Modified Binary Search - Array is rotated but each half is either sorted or contains the rotation point. Check which half is sorted, then decide which half to search based on target's position relative to the sorted half.

Pattern: Binary search with additional logic to handle rotation.

# Given the array nums after rotation and an integer target, return the index
# of target if it is in nums, or -1 if it is not in nums.
# You must write an algorithm with O(log n) runtime complexity.
#
# Example 1:
# Input: nums = [4,5,6,7,0,1,2], target = 0
# Output: 4
#
# Example 2:
# Input: nums = [4,5,6,7,0,1,2], target = 3
# Output: -1
#
# Example 3:
# Input: nums = [1], target = 0
# Output: -1
#
# Constraints:
# 1 <= nums.length <= 5000
# -10^4 <= nums[i] <= 10^4
# All values of nums are unique.
# nums is rotated at some pivot.

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

            # Determine which half is sorted
            if nums[left] <= nums[mid]:
                # Left half is sorted
                if nums[left] <= target < nums[mid]:
                    # Target is in sorted left half
                    right = mid - 1
                else:
                    # Target is in right half
                    left = mid + 1
            else:
                # Right half is sorted
                if nums[mid] < target <= nums[right]:
                    # Target is in sorted right half
                    left = mid + 1
                else:
                    # Target is in left half
                    right = mid - 1

        return -1

# Time Complexity: O(log n)
# Space Complexity: O(1)
#
# Key Insight: At any point, at least one half is sorted
# Steps:
# 1. Identify which half is sorted (compare nums[left] with nums[mid])
# 2. Check if target is in the sorted half
# 3. If yes, search that half; otherwise, search the other half
#
# Why nums[left] <= nums[mid] checks left half sorted?
# - If no rotation in left half, nums[left] <= nums[mid]
# - If rotation exists, nums[mid] < nums[left]