AlgoMaster Logo

Search in Rotated Sorted Array II

mediumUpdated September 21, 2026

Understanding the Problem

We have a sorted array that's been rotated at some unknown pivot point, and it can contain duplicates. Our job is to figure out whether a given target value exists in the array.

This is the follow-up to Search in Rotated Sorted Array, where every element is distinct. With distinct values, binary search can always tell which half of the array is sorted at each step. Duplicates remove that guarantee.

The complication is the case nums[left] == nums[mid] == nums[right]. When all three are equal, the sorted half is undetermined. The left half could be a run of one repeated value with the rotation in the right half, or the right half could be uniform with the rotation on the left. The values alone do not distinguish the two. How the algorithm handles this case determines whether it is correct.

Key Constraints:

  • 1 <= nums.length <= 5000 → An O(n) scan would pass, but the problem asks us to minimize operations, which points to binary search.
  • nums may contain duplicates → This is the constraint that shapes the solution. Duplicates mean binary search on a rotated array cannot always determine which half is sorted.

Approach 1: Linear Scan

Intuition

Walk through the array and check every element. Return true on a match, false after reaching the end.

This ignores the sorted-and-rotated structure, so it does no better than a search on an unsorted array. It serves as a correctness baseline before we use the structure to do better.

Algorithm

  1. Iterate through each element of the array.
  2. If the current element equals the target, return true.
  3. If the loop finishes without finding the target, return false.

Visualization and Code

Loading animation...

The next approach uses the sorted structure to discard half the array at most steps.

Approach 2: Modified Binary Search

Intuition

On a rotated array with distinct values, binary search works because at least one half (left or right of mid) is always fully sorted. We identify the sorted half, check whether the target lies within its value range, and discard the other half.

Duplicates can hide which half is sorted. Take nums = [1, 0, 1, 1, 1] with left = 0, mid = 2, right = 4. All three of nums[left], nums[mid], nums[right] equal 1. The left half [1, 0, 1] is not sorted, the right half [1, 1, 1] is, but the boundary values are identical, so they give no way to decide.

When nums[left] == nums[mid] == nums[right], the algorithm cannot eliminate a half. It instead shrinks the range by one on each side: left++ and right--. This removes one element from each end and makes progress without risking an incorrect elimination. When most elements share a value, every step can hit this case, which degrades the search to O(n). With enough distinct values, the search keeps its O(log n) behavior on average.

For all other cases, the logic is the same as #33:

  • If the left half is sorted (nums[left] <= nums[mid]), check if the target is in [nums[left], nums[mid]). If so, search left. Otherwise, search right.
  • If the right half is sorted (nums[mid] <= nums[right]), check if the target is in (nums[mid], nums[right]]. If so, search right. Otherwise, search left.

Algorithm

  1. Initialize left = 0 and right = nums.length - 1.
  2. While left <= right:
    • Calculate mid = left + (right - left) / 2.
    • If nums[mid] == target, return true.
    • If nums[left] == nums[mid] == nums[right], increment left and decrement right (ambiguous case, can't determine sorted half).
    • Else if the left half is sorted (nums[left] <= nums[mid]):
      • If target >= nums[left] and target < nums[mid], search left: right = mid - 1.
      • Otherwise, search right: left = mid + 1.
    • Else (the right half is sorted):
      • If target > nums[mid] and target <= nums[right], search right: left = mid + 1.
      • Otherwise, search left: right = mid - 1.
  3. If the loop exits without finding the target, return false.

Visualization and Code

Loading animation...