Solving the LeetCode "Search in Rotated Sorted Array II" Problem in Go

Difficulty: Medium | Tags: Array, Binary Search

Introduction

This problem involves searching for a target value in a rotated sorted array that may contain duplicates. The challenge is to efficiently determine whether the target exists in the array while handling the rotation and duplicates.

Problem Analysis

The array is rotated at an unknown pivot, meaning it was originally sorted but then rotated. The presence of duplicates complicates the search because binary search may not always directly narrow down the search space. For example, in [4,5,6,6,7,0,1,2,4,4], searching for 0 requires handling duplicates and rotation.

Solution Approach

The solution involves a modified binary search. Since the array may contain duplicates, we need to handle cases where the middle element equals the left and right bounds. In such cases, we increment the left bound or decrement the right bound to skip duplicates. Otherwise, we determine which half of the array is sorted and check if the target lies within that half.

Go Implementation

func search(nums []int, target int) bool {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return true
        }
        // Handle 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
}

Complexity Analysis

Time Complexity: O(log n) in the best case, but O(n) in the worst case due to duplicates (e.g., all elements are the same). Space Complexity: O(1) as we use constant extra space.

Testing and Examples

Test Case 1: nums = [2,5,6,0,0,1,2], target = 0 → Output: true
Test Case 2: nums = [2,5,6,0,0,1,2], target = 3 → Output: false
Edge Case: nums = [1,1,1,1,1,1,1], target = 2 → Output: false

Best Practices and Tips

1. Always handle duplicates first to avoid incorrect search space reduction.
2. Check if the left or right half is sorted before narrowing the search.
3. Use binary search efficiently to minimize comparisons.