Search in rotated sorted array II

Problem Link

search-in-rotated-sorted-array-ii

Problem Statement

You are given a sorted array nums (in non-decreasing order) that may contain duplicates and has been rotated at an unknown pivot.

Your task is to determine whether a given target is present in the array. Return true if found, else return false.

The goal is to minimize the number of operations performed.

Examples

• Input: nums = [2,5,6,0,0,1,2], target = 0
  Output: true

• Input: nums = [2,5,6,0,0,1,2], target = 3
  Output: false

Constraints

• 1 <= nums.length <= 5000

• -10^4 <= nums[i], target <= 10^4

• nums is guaranteed to be rotated at some pivot

• Duplicates are allowed

Intuition

This is an extension of the Search in Rotated Sorted Array problem. However, due to duplicates, the usual logic of identifying the sorted half becomes ambiguous.

For example:
[1, 0, 1, 1, 1] — we cannot decide which half is sorted when the values are repeated (1 == 1 == 1).

To handle this, we add a pre-check:

• When nums[start] == nums[mid] == nums[end], we cannot determine the sorted half.

• So we move both start and end inward by 1 to skip duplicates.

Approach

1. Initialize start = 0, end = nums.length - 1.

2. Use a modified binary search:

   • Calculate mid = start + (end - start) / 2.

   • If nums[mid] == target, return true.

   • If nums[start] == nums[mid] == nums[end], then increment start and decrement end.

   • Else, determine which half is sorted:

     • If nums[start] <= nums[mid], the left half is sorted:

       • If target lies within [nums[start], nums[mid]], search left.

       • Else, search right.

     • Else, the right half is sorted:

       • If target lies within [nums[mid], nums[end]], search right.

       • Else, search left.

3. If not found, return false.

Java Code

class Solution {
    public boolean search(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (arr[mid] == target) return true;

            // Handle duplicates
            if (arr[start] == arr[mid] && arr[mid] == arr[end]) {
                start++;
                end--;
                continue;
            }

            // Left half is sorted
            if (arr[start] <= arr[mid]) {
                if (arr[start] <= target && target <= arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
            // Right half is sorted
            else {
                if (arr[mid] <= target && target <= arr[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }

        return false;
    }
}

Time and Space Complexity

• Best Case Time Complexity: O(log n) — When no duplicates interfere with binary search decision-making.

• Worst Case Time Complexity: O(n) — When many duplicate elements force linear scanning (start++, end--).

• Space Complexity: O(1) — Constant extra space.

Dry Run

Input:

arr = [2, 5, 6, 0, 0, 1, 2], target = 0

Steps:

1. start = 0, end = 6, mid = 3 → arr[3] = 0
   → Found target → return true

Output: true

Follow-Up: Does the presence of duplicates affect runtime?

Yes.
When duplicates are present, we cannot always determine the sorted half of the array reliably using nums[start], nums[mid], and nums[end].
In such cases, we must shrink the search space linearly (start++, end--), which degrades the time complexity to O(n) in the worst case.

Conclusion

This problem highlights the fragility of binary search when duplicate elements are introduced into a rotated sorted array. The key takeaway is the importance of handling ambiguous cases caused by repeated elements to maintain correctness, even if it compromises time complexity in rare scenarios.

This logic pattern is applicable to many rotated array variations involving duplicates or uncertain boundaries.