Search in Rotated Sorted Array II

Problem Description

Given an integer array nums sorted in non-decreasing order that has been rotated at an unknown pivot, return true if a target exists in nums, or false if it does not.

Key Insights

• The array is sorted but has been rotated, which means it may contain duplicates.
• A modified binary search can be applied to find the target efficiently.
• Care must be taken to handle duplicate values, which can complicate the search by making it harder to determine which part of the array is sorted.

Space and Time Complexity

Time Complexity: O(n) in the worst case due to potential duplicates; O(log n) in average case for unique elements. Space Complexity: O(1) since no additional space is used beyond a few variables.

Solution

To solve this problem, we use a modified binary search approach:

1. Initialize two pointers, left and right, to the start and end of the array, respectively.
2. While left is less than or equal to right:
   • Calculate mid as the average of left and right.
   • If nums[mid] equals the target, return true.
   • If the left half is sorted (i.e., nums[left] <= nums[mid]):
     • Check if the target lies within the sorted range. If so, adjust right to mid - 1, otherwise move left to mid + 1.
   • If the right half is sorted (i.e., nums[mid] <= nums[right]):
     • Check if the target lies within this sorted range. If so, adjust left to mid + 1, otherwise move right to mid - 1.
   • If duplicates are encountered (i.e., nums[left] == nums[mid] or nums[mid] == nums[right]), we cannot determine the sorted part, so increment left and decrement right to skip duplicates.

Code Solutions