LeetCode 81 - Search in Rotated Sorted Array II

LeetCode Problem 81

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

This problem asks us to determine whether a target value exists inside a rotated sorted array that may contain duplicate values.

The original array was sorted in non-decreasing order, meaning values are arranged from smallest to largest, and duplicates are allowed. At some unknown pivot index, the array was rotated. Rotation means the array was split into two parts and swapped in order. For example:

Original: [0,1,2,4,4,5,6]
Rotated : [4,5,6,0,1,2,4]

The task is to return true if the target exists anywhere in the rotated array, otherwise return false.

The key challenge is that duplicates are allowed. In the simpler version of this problem, where all values are distinct, binary search can always determine which half of the array is sorted. With duplicates, this becomes more difficult because equal values can obscure the structure of the rotated array.

The constraints are relatively moderate:

• The array length can be up to 5000
• Values range from -10^4 to 10^4
• The array is guaranteed to have originated from a sorted array and then rotated

Although the input size is not extremely large, the problem explicitly asks us to minimize operation steps, which strongly suggests using binary search rather than linear scanning.

Several edge cases are especially important:

• Arrays containing many duplicates, such as [1,1,1,1,1]
• Arrays where the target appears multiple times
• Arrays where duplicates prevent us from determining the sorted side
• Arrays of length 1
• Arrays that are technically rotated by 0, meaning still fully sorted
• Cases where the target does not exist at all

A naive binary search implementation that assumes distinct values will fail in some duplicate-heavy situations because it may incorrectly identify the sorted half.

Approaches

Brute Force Approach

The simplest solution is to scan the entire array from left to right and compare every element with the target.

If any element equals the target, we return true. If we finish scanning the array without finding the target, we return false.

This approach is always correct because it directly checks every possible candidate. However, it ignores the fact that the array was originally sorted and rotated. As a result, it does not take advantage of the structure of the input.

Its runtime complexity is linear, which is acceptable for the given constraints but not optimal.

Optimal Approach, Modified Binary Search

The better solution uses binary search adapted for rotated arrays with duplicates.

In a normal rotated sorted array without duplicates, binary search works because at least one half of the array is always strictly sorted. We can compare the middle element with the boundaries to determine which half is ordered.

For example:

[4,5,6,7,0,1,2]

If mid is in the left sorted portion, we can determine whether the target lies inside that range.

The complication comes from duplicates. Consider:

[1,1,1,3,1]

If:

left = 0
mid = 2
right = 4

then:

nums[left] == nums[mid] == nums[right]

We cannot determine which side is sorted because duplicates hide the pivot structure.

The key insight is:

• If duplicates prevent us from determining the sorted side, we shrink the search space by moving both boundaries inward
• Otherwise, we proceed with normal rotated-array binary search logic

This preserves correctness while still benefiting from binary search in most cases.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Checks every element sequentially
Optimal	O(log n) average, O(n) worst case	O(1)	Modified binary search that handles duplicates

Algorithm Walkthrough

1. Initialize two pointers, left and right, representing the current search boundaries.
2. Continue searching while left <= right. This guarantees every possible candidate index is considered.
3. Compute the middle index:

mid = (left + right) // 2

4. If nums[mid] == target, immediately return true because the target has been found.
5. Check whether duplicates prevent us from identifying the sorted half:

nums[left] == nums[mid] == nums[right]

If this condition is true, we cannot determine which side is sorted. We shrink the search space safely by:

left += 1
right -= 1

6. Otherwise, determine whether the left half is sorted:

nums[left] <= nums[mid]

If true, the left side is ordered. 7. If the left half is sorted, check whether the target lies inside it:

nums[left] <= target < nums[mid]

• If true, discard the right half:

right = mid - 1

• Otherwise, discard the left half:

left = mid + 1

8. If the left half is not sorted, then the right half must be sorted.
9. Check whether the target lies inside the sorted right half:

nums[mid] < target <= nums[right]

• If true, search the right half:

left = mid + 1

• Otherwise, search the left half:

right = mid - 1

10. If the loop finishes without finding the target, return false.

Python Solution

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return True

            # Cannot determine sorted side because of duplicates
            if nums[left] == nums[mid] == nums[right]:
                left += 1
                right -= 1

            # Left half is sorted
            elif nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1

            # Right half is sorted
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return False

The implementation begins by initializing two pointers that represent the current search interval.

Inside the loop, we compute the middle index and immediately check whether the middle value equals the target. This is the standard binary search stopping condition.

The next section handles the duplicate ambiguity case. When the left, middle, and right values are all equal, we cannot determine which side is sorted. Instead of making an incorrect assumption, we safely shrink the search boundaries.

After removing ambiguous duplicates, we determine whether the left half is sorted. If it is, we check whether the target belongs inside that range. If so, we discard the right half. Otherwise, we discard the left half.

If the left half is not sorted, then the right half must be sorted. We apply the same logic symmetrically.

Eventually, either the target is found or the search space becomes empty.

Go Solution

func search(nums []int, target int) bool {
    left := 0
    right := len(nums) - 1

    for left <= right {
        mid := (left + right) / 2

        if nums[mid] == target {
            return true
        }

        // Cannot determine sorted side because of duplicates
        if nums[left] == nums[mid] && nums[mid] == nums[right] {
            left++
            right--
        } else if nums[left] <= nums[mid] {
            // Left half is sorted
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            // Right half is sorted
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }

    return false
}

The Go implementation follows exactly the same algorithmic structure as the Python version.

Go uses integer division naturally when computing mid, so (left + right) / 2 works correctly.

Unlike Python, Go does not have built-in dynamic lists with type hints, so the function accepts a slice of integers directly.

No special handling for integer overflow is necessary here because the constraints are small, although in larger systems a safer midpoint calculation such as:

mid := left + (right-left)/2

is often preferred.

Worked Examples

Example 1

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

Iteration Trace

left	mid	right	nums[mid]	Action
0	3	6	0	Target found

The target is found immediately at index 3, so the algorithm returns true.

Example 2

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

Iteration 1

left	mid	right	nums[mid]
0	3	6	0

The right half [0,1,2] is sorted.

Check whether target 3 lies inside:

0 < 3 <= 2

This is false, so discard the right half.

Update:

right = mid - 1 = 2

Iteration 2

left	mid	right	nums[mid]
0	1	2	5

The left half [2,5] is sorted.

Check whether target 3 lies inside:

2 <= 3 < 5

This is true.

Update:

right = mid - 1 = 0

Iteration 3

left	mid	right	nums[mid]
0	0	0	2

Target not found.

Duplicates condition applies because:

nums[left] == nums[mid] == nums[right]

Shrink boundaries:

left = 1
right = -1

Loop terminates.

Return false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n) average, O(n) worst case	Binary search normally halves the search space, but duplicates can force linear shrinking
Space	O(1)	Only a few pointer variables are used

In the average case, the algorithm behaves similarly to standard binary search and discards half the search space each iteration.

However, duplicates can degrade performance. In the worst case, arrays such as:

[1,1,1,1,1,1,1]

force the algorithm to shrink the boundaries one step at a time because it cannot determine which side is sorted. This leads to linear time complexity.

The algorithm uses constant extra space because it only maintains index pointers.

Edge Cases

Array Containing Only Duplicates

Consider:

nums = [1,1,1,1,1]
target = 1

A standard rotated-array binary search may fail because every comparison looks identical. The implementation handles this by shrinking both boundaries whenever the left, middle, and right values are equal.

This guarantees progress and eventually finds the target.

Target Does Not Exist

Consider:

nums = [2,2,2,3,4,2]
target = 5

The algorithm repeatedly narrows the search range until the interval becomes empty.

It correctly returns false without requiring a full linear scan in most cases.

Single Element Array

Consider:

nums = [1]
target = 1

The algorithm computes:

mid = 0

and immediately returns true.

For:

nums = [1]
target = 2

the loop exits after one iteration and returns false.

Rotation Near the Ends

Consider:

nums = [1,2,3,4,5]

or:

nums = [5,1,2,3,4]

The algorithm correctly handles both minimal and maximal rotation positions because the sorted-half detection logic works regardless of pivot placement.

Duplicate Values Around the Pivot

Consider:

nums = [1,0,1,1,1]
target = 0

This is a classic tricky case. Duplicates hide the pivot structure, but the duplicate-shrinking step eventually exposes enough structure for binary search to proceed correctly.