Search in Rotated Sorted Array II | Leetcode 81

Welcome to our deep dive on Search in Rotated Sorted Array II (Leetcode 81). This is a tricky extension of a classic binary search problem that introduces annoying duplicate numbers.

Problem Statement

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index. Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

Example: nums = [2,5,6,0,0,1,2], target = 0 => Output: true

Approach: Tricky Modified Binary Search O(N) Worst Case

When the array doesn't have duplicates, we can easily check whether the left half or right half of our mid pointer is strictly sorted.

However, with duplicates, we can hit a situation where nums[left] == nums[mid] == nums[right]. In this exact scenario, we cannot determine which half is sorted! The only safe move is to simply shrink both bounds inward by one (left++ and right--) and meticulously try again.

1. Maintain standard left and right pointers.
2. Calculate mid = (left + right) // 2.
3. If nums[mid] == target, we found it! Return true.
4. The Duplicate Case: If nums[left] == nums[mid] == nums[right], increment left and decrement right.
5. Standard Left-Sorted Check: nums[left] <= nums[mid].
   • If the target falls into this sorted left half, bring right = mid - 1.
   • Otherwise, push left = mid + 1.
6. Standard Right-Sorted Check: The right half must be the sorted one.
   • If target falls into this sorted right half, bring left = mid + 1.
   • Otherwise, push right = mid - 1.

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                return True
                
            # The tricky duplicate case
            if nums[left] == nums[mid] and nums[mid] == nums[right]:
                left += 1
                right -= 1
                continue
                
            # Left half is sorted
            if 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

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (81)