NUHMAN.com

Introduction

LeetCode 81: Search in Rotated Sorted Array II is a follow-up to the classic rotated array search (LeetCode 33), but this time, the array may contain duplicates.

This twist complicates the traditional binary search algorithm and requires careful handling of ambiguity. It's a great problem to deepen your understanding of binary search edge cases and sorted array behavior under transformation.

Problem Statement

Given an integer array nums sorted in non-decreasing order and rotated at an unknown pivot, and a target value, return true if target is in the array, and false otherwise.

The array may contain duplicates.

Example:

go

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

Approach: Modified Binary Search with Duplicates

Key Observations:

• In a rotated array without duplicates, we can always determine which half is sorted.
• Duplicates obscure the sorted half when nums[low] == nums[mid] == nums[high], so we need to carefully skip duplicates.

Algorithm Steps:

1. Use classic binary search (low, high, mid).
2. If nums[mid] == target, return true.
3. If duplicates are found at low, mid, and high → increment low and decrement high.
4. If the left half is sorted, check if the target is in that range.
5. Otherwise, check the right half.

Go Implementation

go

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

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

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

        // Skip duplicates
        if nums[low] == nums[mid] && nums[mid] == nums[high] {
            low++
            high--
        } else 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
}

Explanation

• We’re applying a binary search, but accounting for ambiguous sections due to duplicates.
• When encountering nums[low] == nums[mid] == nums[high], we increment and decrement both ends to skip unnecessary comparisons.
• This ensures we don't get stuck in an infinite loop and eventually narrow down to a sorted segment.

Time and Space Complexity

MetricComplexityTime ComplexityO(log n) average, O(n) worst (due to duplicates)Space ComplexityO(1)

The worst-case time is linear when all elements are the same (e.g., [1,1,1,1,1]).

Edge Cases

• Empty array → return false.
• Single element matching target → true.
• Duplicates at the edges → must be skipped.
• All elements same but target not present → return false.

Conclusion

LeetCode 81 is a fantastic twist on binary search. It forces you to think critically about edge cases introduced by duplicate values in rotated arrays.

This problem strengthens your Go skills in:

• Efficient loop control
• Conditional branching
• Avoiding infinite loops due to ambiguous comparisons