Search in Rotated sorted Array II

81.Search in Rotated Sorted Array II

Array

Binary Search

Divide and Conquer

Problem Statement:

Given a sorted array nums that is rotated at some pivot index and may contain duplicates, return true if target exists in the array, and false otherwise.

Example:

Input:

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

→

Output:

true

Algorithm:

1. Handle duplicates by skipping when left = mid = right
2. Identify sorted half using strict inequalities
3. Search in appropriate half based on target
4. Move pointers for sorted vs unsorted halves

Complexity:

Time: O(n) worst case with duplicates, O(log n) average | Space: O(1)

Java Solution:

public boolean search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left)/2;
        
        // Found target
        if (nums[mid] == target) return true;
        
        // Left side is sorted or right is unsorted
        if (nums[left] < nums[mid] || nums[mid] > nums[right]) {
            // Check if target is in left sorted portion
            if (target < nums[mid] && target >= nums[left])
                right = mid - 1;
            else
                left = mid + 1;
            
        // Right side is sorted or left is unsorted
        } else if (nums[mid] < nums[right] || nums[mid] < nums[left]) {
            // Check if target is in right sorted portion
            if (target > nums[mid] && target <= nums[right])
                left = mid + 1;
            else
                right = mid - 1;
                
        // Handle duplicates when nums[left] = nums[mid] = nums[right]
        } else {
            left++;
            right--;
        }
    }
    
    return false;
}

Python Solution:

def search(self, nums: List[int], target: int) -> bool:
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        # Found target
        if nums[mid] == target:
            return True
            
        # Left side is sorted or right is unsorted
        if nums[left] < nums[mid] or nums[mid] > nums[right]:
            # Check if target is in left sorted portion
            if target < nums[mid] and target >= nums[left]:
                right = mid - 1
            else:
                left = mid + 1
                
        # Right side is sorted or left is unsorted
        elif nums[mid] < nums[right] or nums[mid] < nums[left]:
            # Check if target is in right sorted portion
            if target > nums[mid] and target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
                
        # Handle duplicates
        else:
            left += 1
            right -= 1
            
    return False

C++ Solution:

bool search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left)/2;
        
        // Found target
        if (nums[mid] == target) return true;
        
        // Left side is sorted or right is unsorted
        if (nums[left] < nums[mid] || nums[mid] > nums[right]) {
            // Check if target is in left sorted portion
            if (target < nums[mid] && target >= nums[left])
                right = mid - 1;
            else
                left = mid + 1;
                
        // Right side is sorted or left is unsorted
        } else if (nums[mid] < nums[right] || nums[mid] < nums[left]) {
            // Check if target is in right sorted portion
            if (target > nums[mid] && target <= nums[right])
                left = mid + 1;
            else
                right = mid - 1;
                
        // Handle duplicates
        } else {
            left++;
            right--;
        }
    }
    
    return false;
}