Search In Rotated Sorted Array Ii

To solve this coding challenge, we can use a modified binary search algorithm to adapt it to the properties of a rotated sorted array, even if the array contains duplicates. The key steps involve adjusting the binary search conditions to handle the potential duplicate values and ensuring that we search in the correct half of the rotated array. Firstly, let's break down the problem. Given a rotated sorted array
nums
, we need to determine whether a target value exists within this array. The array was rotated at an unknown pivot point, and it contains elements that are non-distinct.

Explanation:

  1. Initialization : Start with two pointers (
    left
    and
    right
    ), which point to the beginning and the end of the array, respectively.
  2. Binary Search Loop : Use a while loop to perform binary search until
    left
    exceeds
    right
    .
  3. Middle Calculation : Calculate the middle index
    mid
    . This index will help us determine if we need to search in the left or right half of the array.
  4. Target Check : If
    nums[mid]
    equals the target, return
    True
    immediately.
  5. Handle Duplicates : If
    nums[left]
    equals
    nums[mid]
    , increment the
    left
    pointer to skip duplicates. This step is crucial to handle the situation where duplicates might be at the edges of our current search window, potentially misleading the determination of which half is sorted.
  6. Left Sorted Half : If
    nums[left]
    is less than or equal to
    nums[mid]
    , it means the left half of the array is sorted:
    • Check if the target lies within the range of
      nums[left]
      and
      nums[mid]
      .
    • If it does, adjust the
      right
      pointer to search in the left half.
    • Otherwise, adjust the
      left
      pointer to search in the right half.
  7. Right Sorted Half : If
    nums[mid]
    is less than
    nums[right]
    , it means the right half is sorted:
    • Check if the target lies within the range of
      nums[mid]
      and
      nums[right]
      .
    • If it does, adjust the
      left
      pointer to search in the right half.
    • Otherwise, adjust the
      right
      pointer to search in the left half.
  8. Terminate and Return : If the target is found, return
    True
    . If the loop exits without finding the target, return
    False
    .

    9. Detailed Steps in Pseudocode:

  9. Initialize variables : 
      10.                                             
left = 0        # Starting index of the array
right = len(nums) - 1  # Last index of the array
  10. Binary Search Loop : 
      11.                                             
WHILE left <= right:
mid = (left + right) // 2  # Calculate the middle index

IF nums[mid] == target:
RETURN True  # Target found at the mid index

# Handle duplicates
WHILE left < mid AND nums[left] == nums[mid]:
left += 1  # Move left pointer to skip duplicates

# Check if the left half is sorted
IF nums[left] <= nums[mid]:
IF nums[left] <= target < nums[mid]:
right = mid - 1  # Target is in the left half
ELSE:
left = mid + 1  # Target is in the right half

# Check if the right half is sorted
ELSE:
IF nums[mid] < target <= nums[right]:
left = mid + 1  # Target is in the right half
ELSE:
right = mid - 1  # Target is in the left half
  11. Terminate and Return : 
      12.                                             
RETURN False  # Target not found in the array
Overall, this solution leverages the binary search algorithm, with modifications to accommodate the rotated nature of the array and the presence of duplicate elements. Through each iteration, the search range is progressively narrowed down, ensuring logarithmic time complexity efficiency.