Binary Search - Search Element in Rotated Sorted Array II

This chapter covers how to search for a target element in a rotated sorted array that contains duplicate elements. Building directly upon the foundation of searching in a rotated sorted array with unique elements, we will analyze why duplicates break the standard binary search assumptions and how to adapt our algorithm to handle these edge cases efficiently.

1. The Problem Statement & Context

In Search in Rotated Sorted Array I, we were given a rotated sorted array of unique elements and had to return the index of a target element.

In Search in Rotated Sorted Array II, the problem introduces a critical twist: the array may contain duplicate elements. Because of these duplicates, returning a unique index is not always possible in $O(\log N)$ time. Therefore, the objective is simplified to returning a boolean value:

• Return true if the target element exists in the array.
• Return false if the target element does not exist in the array.

Why We Cannot Return the Index

If an array contains duplicates (e.g., [3, 3, 1, 3, 3, 3] with target 3), the target exists at multiple indices. Finding a specific index or all indices of a duplicate element using pure binary search is not possible in logarithmic time; a linear scan would be required. Thus, the problem restricts the output to a simple existence check (true/false).

2. Recap: The Unique Elements Approach (Part I)

To understand why duplicates cause failure, we must first review the core mental model of the unique elements approach.

The Core Principle

In any rotated sorted array, when you split the array at any arbitrary midpoint (mid), at least one half (either the left half or the right half) is guaranteed to be sorted.

The Algorithm for Unique Elements

1. Find the middle element mid.
2. Check if arr[mid] == target. If yes, return its index.
3. Identify which half is sorted:
   • If the left half is sorted (arr[low] <= arr[mid]): Check if the target lies within the range [arr[low], arr[mid]]. If it does, eliminate the right half (high = mid - 1). Otherwise, eliminate the left half (low = mid + 1).
   • If the right half is sorted (arr[mid] <= arr[high]): Check if the target lies within the range [arr[mid], arr[high]]. If it does, eliminate the left half (low = mid + 1). Otherwise, eliminate the right half (high = mid - 1).

3. Why the Unique Logic Fails on Duplicates

The fundamental assumption of the unique elements algorithm is that we can always identify the sorted half by comparing arr[low] with arr[mid] and arr[mid] with arr[high]. Duplicates break this assumption.

The "Three-Way Equal" Ambiguity

Consider the following rotated sorted array containing duplicates:

Let's place our pointers:

• low points to index 0 (value = 3)
• high points to index 6 (value = 3)
• mid points to index 3 (value = 3)

Index:    0    1    2    3    4    5    6
Value:  [ 3,   3,   0,   3,   3,   3,   3 ]
          ^              ^              ^
         low            mid            high

Now, let's try to determine which half is sorted:

• Left comparison: Is arr[low] <= arr[mid]? ($3 \le 3$ is True). This suggests the left half is sorted.
• Right comparison: Is arr[mid] <= arr[high]? ($3 \le 3$ is True). This suggests the right half is sorted.

Both conditions evaluate to true. However, looking at the actual elements:

• The left half [3, 3, 0, 3] is not sorted (it dips down to 0).
• The right half [3, 3, 3, 3] is sorted.

Programmatically, the algorithm cannot distinguish which half is genuinely sorted because:

Without knowing which half is sorted, we cannot safely eliminate half of the search space.

4. The Solution: Shrinking the Search Space

To resolve this ambiguity, we must handle the specific edge case where the boundary elements and the middle element are all equal.

The Intuition

If $\text{arr[low]} == \text{arr[mid]} == \text{arr[high]}$, and we have already checked that $\text{arr[mid]} \neq \text{target}$, then it logically follows that:

• $\text{arr[low]}$ is not the target.
• $\text{arr[high]}$ is not the target.

Since neither boundary element can be our target, we can safely discard them from our search space by shrinking the boundaries inward:

• Increment low by 1 (low++)
• Decrement high by 1 (high--)

Initial State:
[ 3,   3,   0,   3,   3,   3,   3 ]
  ^              ^              ^
 low            mid            high

Since arr[low] == arr[mid] == arr[high] == 3 (and target != 3):
Shrink boundaries: low++ and high--

New State:
[ 3,   3,   0,   3,   3,   3,   3 ]
       ^         ^         ^
      low       mid       high

By shrinking the boundaries, we eliminate the ambiguous duplicates at the edges. In the next iteration, we recalculate mid and check if we can now identify the sorted half. We repeat this shrinking process until $\text{arr[low]} \neq \text{arr[mid]}$ or $\text{arr[mid]} \neq \text{arr[high]}$.

5. Step-by-Step Algorithm Evolution

Here is how we modify the standard rotated sorted array binary search to handle duplicates:

6. Code Implementations

Below are the complete, production-grade implementations in C++, Java, and Python.

C++ Code

#include <vector>

class Solution {
public:
    bool search(std::vector<int>& nums, int target) {
        int low = 0;
        int high = nums.size() - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            // 1. Check if mid is the target
            if (nums[mid] == target) {
                return true;
            }

            // 2. Handle the duplicate ambiguity edge case
            if (nums[low] == nums[mid] && nums[mid] == nums[high]) {
                low = low + 1;
                high = high - 1;
                continue; // Skip to the next iteration to re-evaluate
            }

            // 3. Identify the sorted half
            if (nums[low] <= nums[mid]) {
                // Left half is sorted
                if (nums[low] <= target && target <= nums[mid]) {
                    high = mid - 1; // Target is in the left half
                } else {
                    low = mid + 1;  // Target is in the right half
                }
            } else {
                // Right half is sorted
                if (nums[mid] <= target && target <= nums[high]) {
                    low = mid + 1;  // Target is in the right half
                } else {
                    high = mid - 1; // Target is in the left half
                }
            }
        }
        return false;
    }
};

Java Code

public class Solution {
    public boolean search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            // 1. Check if mid is the target
            if (nums[mid] == target) {
                return true;
            }

            // 2. Handle the duplicate ambiguity edge case
            if (nums[low] == nums[mid] && nums[mid] == nums[high]) {
                low = low + 1;
                high = high - 1;
                continue;
            }

            // 3. Identify the sorted half
            if (nums[low] <= nums[mid]) {
                // Left half is sorted
                if (nums[low] <= target && target <= nums[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else {
                // Right half is sorted
                if (nums[mid] <= target && target <= nums[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        return false;
    }
}

Python Code

class Solution:
    def search(self, nums: list[int], target: int) -> bool:
        low, high = 0, len(nums) - 1

        while low <= high:
            mid = low + (high - low) // 2

            # 1. Check if mid is the target
            if nums[mid] == target:
                return True

            # 2. Handle the duplicate ambiguity edge case
            if nums[low] == nums[mid] and nums[mid] == nums[high]:
                low += 1
                high -= 1
                continue

            # 3. Identify the sorted half
            if nums[low] <= nums[mid]:
                # Left half is sorted
                if nums[low] <= target <= nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            else:
                # Right half is sorted
                if nums[mid] <= target <= nums[high]:
                    low = mid + 1
                else:
                    high = mid - 1

        return False

7. Complete Flow Walkthrough (Dry Run)

Let us dry run the algorithm with an edge-case array.

Input Parameters

• nums = [3, 1, 2, 3, 3, 3, 3]
• target = 1

Execution Steps

Iteration 1

• Pointers: low = 0, high = 6
• Calculate Mid: mid = 0 + (6 - 0) / 2 = 3
• Values: nums[low] = 3, nums[mid] = 3, nums[high] = 3
• Step 1: Is nums[mid] == target? ($3 == 1$ is False).
• Step 2 Check Edge Case: Is nums[low] == nums[mid] == nums[high]?
  • $3 == 3 == 3$ is True.
  • Action: Shrink search space.
    • low = low + 1 $\rightarrow$ 1
    • high = high - 1 $\rightarrow$ 5
  • continue to next iteration.

Array: [ 3,   1,   2,   3,   3,   3,   3 ]
              ^         ^         ^
             low       mid       high

Iteration 2

• Pointers: low = 1, high = 5
• Calculate Mid: mid = 1 + (5 - 1) / 2 = 3
• Values: nums[low] = 1, nums[mid] = 3, nums[high] = 3
• Step 1: Is nums[mid] == target? ($3 == 1$ is False).
• Step 2 Check Edge Case: Is nums[low] == nums[mid] == nums[high]?
  • $1 == 3 == 3$ is False.
• Step 3 Identify Sorted Half:
  • Is nums[low] <= nums[mid]? ($1 \le 3$ is True). Left half is sorted.
  • Is target within left sorted half? Is nums[low] <= target <= nums[mid]?
    • $1 \le 1 \le 3$ is True.
    • Action: Eliminate right half.
      • high = mid - 1 $\rightarrow$ 3 - 1 = 2

Array: [ 3,   1,   2,   3,   3,   3,   3 ]
              ^    ^
             low  high

Iteration 3

• Pointers: low = 1, high = 2
• Calculate Mid: mid = 1 + (2 - 1) / 2 = 1
• Values: nums[low] = 1, nums[mid] = 1, nums[high] = 2
• Step 1: Is nums[mid] == target? ($1 == 1$ is True).
• Result: Return true.

8. Complexity Analysis

9. General Strategy for Duplicate Problems in Binary Search

When solving binary search problems that involve duplicate elements, use this systematic three-step framework:

Summary and Key Takeaways

• The Core Issue: Duplicates introduce ambiguity because the condition $\text{arr[low]} == \text{arr[mid]} == \text{arr[high]}$ makes it programmatically impossible to determine which half of the rotated array is sorted.
• The Solution: When this ambiguity occurs, shrink the search space by incrementing low and decrementing high by $1$, then continue the search.
• Safety of Shrinking: Shrinking is safe because we check if arr[mid] == target at the start of each iteration. If arr[mid] is not the target, then neither arr[low] nor arr[high] can be the target when they are equal to arr[mid].
• No Index Guarantee: Due to duplicates, we only return a boolean (true/false) indicating existence, rather than a specific index.
• Performance Trade-off: While the average-case time complexity remains logarithmic ($\mathcal{O}(\log N)$), the worst-case time complexity degrades to linear ($\mathcal{O}(N)$) when the array is dominated by duplicates.
• Systematic Approach: Always solve duplicate-based binary search problems by first writing the solution for unique elements, identifying where duplicates break the logic, and then adding boundary-shrinking conditions to handle those edge cases.