Search in Rotated Sorted Array II

Language Options

Problem Description

Ah, the classic “Search in Rotated Sorted Array II” problem! Imagine you’re at a party, and someone has decided to rearrange all the chairs in a circle. You know there are a certain number of chairs (or elements) and that they were originally in a nice, orderly line (sorted). But now, some genius has rotated them, and you need to find a specific chair (or target value) among this chaotic arrangement.

In more technical terms, you are given a rotated sorted array that may contain duplicates, and your task is to determine if a specific target value exists in that array. Sounds simple, right? Well, it’s like trying to find your friend in a crowd of people wearing the same outfit!

Code Solution


class Solution:
    def search(self, nums: list[int], target: int) -> bool:
        l = 0
        r = len(nums) - 1

        while l <= r:
            m = (l + r) // 2
            if nums[m] == target:
                return True
            if nums[l] == nums[m] == nums[r]:
                l += 1
                r -= 1
            elif nums[l] <= nums[m]:  # nums[l..m] are sorted
                if nums[l] <= target < nums[m]:
                    r = m - 1
                else:
                    l = m + 1
            else:  # nums[m..n - 1] are sorted
                if nums[m] < target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1

        return False

Approach Explanation

The approach here is a modified binary search. We start with two pointers, l and r, representing the left and right bounds of our search space. The middle index m is calculated, and we check if the middle element is our target. If the left, middle, and right elements are the same, we increment both pointers to skip duplicates.

If the left half is sorted, we check if the target lies within that range. If it does, we adjust our right pointer; otherwise, we move our left pointer. If the right half is sorted, we do the opposite. This continues until we either find the target or exhaust our search space.

Time and Space Complexity

Time Complexity

O(n) in the worst case due to the possibility of encountering duplicates, which may force us to check every element.

Space Complexity

O(1) since we are using a constant amount of space for our pointers.

Real-World Example

Imagine you’re at a buffet, and the food is arranged in a circular table. You know there are delicious dishes (elements) but they’ve been rotated around the table. You’re on a mission to find the lasagna (target). You can’t just walk straight to it because there are other dishes in the way, and some of them look suspiciously similar (duplicates). You have to navigate through the chaos, using your keen sense of smell (binary search) to locate that cheesy goodness!