33.Search_in_Rotated_Sorted_Array(Medium).md

33. Search in Rotated Sorted Array (Medium)

Date and Time: Jul 19, 2024, 14:57 (EST)

Link: https://leetcode.com/problems/search-in-rotated-sorted-array/

Question:

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible 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

Edge case:

Input: nums=[3,1], target = 1

Output: 1

Constraints:

• 1 <= nums.length <= 5000

• -10^4 <= nums[i] <= 10^4

• All values of nums are unique.

• nums is an ascending array that is possibly rotated.

• -10^4 <= target <= 10^4

KeyPoints:

Very similar to 153. Find Minimum in Rotated Sorted Array. There are two cases of nums:

nums[l] <= nums[m]: [3, 4, 5, 0, 1], [0, 1, 2, 3, 4]. We are sure that [l, m] is sorted, so we search the left of m if nums[l] <= target < nums[m] by updating r = m - 1. Otherwise, we update l = m + 1.

nums[l] > nums[m]: [5, 1, 3], [6, 0, 1, 2, 3]. It ensures that [m, r] is sorted, we search the right of m if nums[m] < target <= nums[r] by updating l = m + 1. Otherwise, we update r = m - 1.

My Solution:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # if nums[l] <= nums[m]: [l, mid] is sorted
        # Only check left if nums[l] <= target < nums[m]
        # Else: check right

        # If nums[l] > nums[m]: only make sure [m, r] is sorted
        # Only check right if nums[m] < target <= nums[m]
        # Else: check right

        # TC: O(log(n)), n=len(nums), SC: O(1)
        l, r = 0, len(nums)-1
        while l <= r:
            m = (l+r) // 2
            if nums[m] == target:
                return m
            # [l, m] is sorted
            if nums[l] <= nums[m]:
                # Search the left of m
                if target < nums[m] and target >= nums[l]:
                    r = m - 1
                else:
                    l = m + 1
            # [m, r] is sorted
            else:
                # Search the right of m
                if target > nums[m] and target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1
        return -1

Time Complexity: $O(log\ n)$
Space Complexity: $O(1)$