algoadvance

Problem Description

You are given an integer array nums sorted in ascending order (with possible duplicates), and an integer target. Suppose the array is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). This means that the array has been split into two sorted subarrays and then recombined.

You should write a function to determine if target is in nums. If target exists in nums, return true. Otherwise, return false.

Clarifying Questions

  1. Q: What should be the return type? A: The function should return a boolean indicating whether the target is present in the array.

  2. Q: Can the array have duplicate elements? A: Yes, the array can have duplicate elements.

  3. Q: Is there a constraint on the length of the input array? A: The length of the array can vary but typically falls within reasonable bounds for typical algorithm problems (e.g., length n where 0 <= n <= 5000).

Strategy

To solve the problem, we can adapt binary search, which commonly has a time complexity of O(log n) in a regular sorted array. However, due to the presence of duplicates, the worst-case time complexity can degrade to O(n). Here’s the strategy in detail:

  1. Initialize two pointers, left and right, to the start and end of the array.
  2. Perform binary search by calculating the midpoint mid.
  3. Check if nums[mid] is equal to target. If true, return True.
  4. To handle the rotation, determine which part of the array is sorted:
    • If nums[left] < nums[mid], then the left part is sorted.
    • If nums[left] > nums[mid], then the right part must be sorted.
    • If nums[left] == nums[mid], increment the left pointer to skip duplicates.
  5. Depending on whether the left or right part is sorted and where the target lies relative to nums[mid], adjust left and right pointers accordingly.

Time Complexity

The worst-case time complexity is O(n) due to the potential need to linearly skip duplicates.

Implementation

Here’s the Python code implementing the above strategy:

def search(nums, target):
    if not nums:
        return False
    
    left, right = 0, nums.length - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return True
        
        # Handling duplicates
        while left < mid and nums[left] == nums[mid]:
            left += 1
        
        # If the left part is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # If the right part is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return False

# Example usage:
# nums = [2, 5, 6, 0, 0, 1, 2]
# target = 0
# print(search(nums, target))  # Output: True

This code will help determine if the target exists in the rotated sorted array with duplicates.

Try our interview co-pilot at AlgoAdvance.com