We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Search in Rotated Sorted Array II

Number: 81

Difficulty: Medium

Paid? No

Companies: Meta, Google, Amazon, Walmart Labs, Microsoft, Bloomberg, Apple, Uber

Problem Description

Given a rotated sorted array (which may contain duplicate elements) and an integer target, determine if the target exists in the array. The array is originally sorted in non-decreasing order and then rotated at an unknown pivot. The challenge is to reduce the overall operational steps as much as possible.

Key Insights

  • The array is rotated, so one of the two halves will always be sorted.
  • Duplicates can complicate the binary search by obscuring which half is sorted.
  • When duplicates cause ambiguity (i.e., when nums[low], nums[mid], and nums[high] are equal), the search space is reduced by incrementally moving the boundaries.
  • A modified binary search can efficiently search the array on average, though the worst-case runtime can degrade to O(n) due to duplicates.

Space and Time Complexity

Time Complexity: Worst-case O(n), Average-case O(log n)
Space Complexity: O(1)

Solution

The solution employs a modified binary search technique. The main algorithm works by maintaining two pointers (low and high) and calculating a mid-point. If the target is equal to the element at the mid, the algorithm returns true. If duplicates are detected at the low, mid, and high indices, the boundaries are adjusted to avoid ambiguity. Otherwise, the algorithm determines if the left or right side is sorted; if the target lies within the sorted portion, it moves the boundaries accordingly. This method accounts for potential duplicate values influencing the decision process.

Code Solutions

# Function to search for the target in a rotated sorted array that may contain duplicates.
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        low, high = 0, len(nums) - 1  # Initialize two pointers.
        
        while low <= high:
            mid = (low + high) // 2  # Find the mid-point.
            if nums[mid] == target:  # If the mid element is the target, return True.
                return True
            
            # If the values at low, mid, and high are equal, we cannot decide which half is sorted.
            if nums[low] == nums[mid] == nums[high]:
                low += 1  # Shrink the search window.
                high -= 1
            # If the left half is sorted.
            elif nums[low] <= nums[mid]:
                if nums[low] <= target < nums[mid]:  # Check if target is in the left half.
                    high = mid - 1
                else:
                    low = mid + 1
            # Otherwise, the right half must be sorted.
            else:
                if nums[mid] < target <= nums[high]:  # Check if target is in the right half.
                    low = mid + 1
                else:
                    high = mid - 1
        
        return False  # Target not found.
← Back to All Questions