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/

Access Time
Jun 11, 25

Walk-through:

Very similar to 153. Find Minimum in Rotated Sorted Array.

We can run binary search to find the median and compare it with the boundary (nums[l], nums[r]) to know which part is sorted and check whether we should check on the left or right side. If nums[m] >= nums[l], then we know [l, m] is sorted, and we check if target <= nums[l] and target < nums[m] to know if target is within [l, m], if so, update r ptr to search on m's left. Otherwise, check on m's right.

1. Find median

2. Use median to compare boundaries l, r, which are nums[0], nums[len(nums)-1], to know which side is sorted.

3. Check if target is within the sorted side, if so, update ptr and search on there. Otherwise, check on the another half.

There are two cases of nums:

nums[l] <= nums[m]: [4, 5, 0, 1, 2, 3], [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.

Solution

Jun 7, 2026
1. First check if the left subarray [l, m] or the right subarray [m, r] is sorted. 2. If [l, m] is sorted, check target is within [l, m] or the right side of m.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # Q: Find the index of target in rotated nums
        # S: Binary Search: compare val with target, and the boundary values nums[l] and nums[r], l = 0 and r = len(nums)-1.
        # 1. if nums[m] == target: return index.
        # 2. if nums[m] <= nums[l]: [m, len(nums)-1] is sorted, check if we should search on the right-side by checking nums[m] < target <= nums[r].
        # 3. if nums[m] > nums[r]: [l, m] is sorted, check if we should search on the left-side by checking nums[l] <= target < nums[m].
        # TC: O(log(n)), n=len(nums), SC: O(1)

        l, r = 0, len(nums)-1
        while l <= r:
            m = (l + r) // 2
            # Compare medium with l, r boundaries
            if nums[m] == target:
                return m
            # [l, m] is sorted
            elif nums[m] >= nums[r]:
                # Check if target is within left subarray
                if nums[l] <= target < nums[m]:
                    r = m - 1
                else:
                    l = m + 1
            # [m ,r] is sorted
            else:
                # Check if target is within right subarray
                if nums[m] < target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1
        return -1

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