Try the Question

Before reading the explanation, try solving the problem yourself:

👉 https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

Practicing the problem first helps develop stronger problem-solving intuition, especially for binary search variations.

Problem Statement

You are given an integer array nums that is sorted in non-decreasing order.

Example of a sorted array:

Before being passed to your function, the array may be rotated at some pivot index k.

After rotation, the structure becomes:

Example:

You are also given an integer target.

Your task is to determine:

1. Return true if the target exists in the array
2. Return false if the target does not exist

The goal is to minimize the number of operations, which suggests using Binary Search.

Example Walkthrough

Example 1

Input

Output

Explanation:

Example 2

Input

Output

Explanation:

Understanding the Core Challenge

This problem is very similar to the classic problem:

Search in Rotated Sorted Array (LeetCode 33).

However, there is an important difference.

Difference Between the Two Problems

Duplicates introduce ambiguity during binary search.

Why Duplicates Make the Problem Harder

In the previous problem, we relied on this rule:

But duplicates can break this assumption.

Example:

If:

Then:

Here we cannot determine which half is sorted.

This is the main complication introduced by duplicates.

Key Idea to Handle Duplicates

When the values at left, mid, and right are the same, the algorithm cannot decide which half is sorted.

To resolve this situation, we shrink the search space:

This gradually removes duplicate values and allows binary search to continue.

Modified Binary Search Strategy

The algorithm works as follows:

Step 1

Calculate the middle index.

Step 2

If the middle element equals the target:

Step 3

If duplicates block decision-making:

Then move both pointers inward:

Step 4

Otherwise, determine which half is sorted and apply normal binary search logic.

Java Implementation

Step-by-Step Example

Array:

Iteration 1

Target found immediately.

Time Complexity

Best Case

When duplicates do not interfere with binary search decisions.

Worst Case

When many duplicate values force the algorithm to shrink the search space one element at a time.

Example worst case:

Binary search cannot divide the array effectively.

Space Complexity

The algorithm only uses a few variables and does not require extra memory.

Follow-Up: How Do Duplicates Affect Runtime?

Without duplicates, binary search always reduces the search space by half.

With duplicates, we sometimes cannot determine which half is sorted.

In such cases, we shrink the search space linearly:

This may degrade performance to:

However, in most practical cases the algorithm still performs close to logarithmic time.

Key Takeaways

✔ The array is sorted but rotated

✔ Duplicates introduce ambiguity in binary search

✔ Special handling is required when nums[left] == nums[mid] == nums[right]

✔ The algorithm combines binary search with duplicate handling

✔ Worst-case complexity may degrade to O(n)

Final Thoughts

This problem is a natural extension of the rotated sorted array search problem. It tests your ability to adapt binary search to more complex conditions.

Understanding this pattern is valuable because similar techniques appear in many interview problems involving:

1. Rotated arrays
2. Binary search edge cases
3. Handling duplicates in sorted data structures

Mastering this approach strengthens both algorithmic thinking and interview preparation.