Search in Rotated Sorted Array II | Leetcode 81 | Optimal Binary Search

The “Search in Rotated Sorted Array II” problem is a classic coding interview question that tests your understanding of binary search and handling duplicates in arrays. In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.

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 k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

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.

You must decrease the overall operation steps as much as possible.

Here’s the [Problem Link] to begin with.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• nums is guaranteed to be rotated at some pivot.
• -104 <= target <= 104

Follow up: This problem is similar to Search in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

Brute Force Solution (Linear Search)

Intuition and Approach

Let’s solve the problem in the most straightforward way:

1. Scan Each Element:
   Go through the array from start to end.
2. Check for Target:
   If any element matches the target, return True.
3. Why does this work?
   We check every element, so we won’t miss the target if it’s there.

This approach is easy to understand but not efficient for large arrays.

Code Implementation

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        for i in range(len(nums)):               # Scan each index one by one
            if nums[i] == target:                # If the current element matches target
                return True                      # Return True immediately
        return False                             # If not found, return False

Code Explanation

• We loop through each element in the array.
• If we find the target, we return True.
• If we reach the end without finding it, we return False.

Dry Run

Input:
nums = [1], target = 0

• Check 2: not target
• Check 5: not target
• Check 6: not target
• Check 0: found! Return True

Final Output:
True

Time and Space Complexity

• Time Complexity: O(n)
  We may have to check every element.
• Space Complexity: O(1)
  Only a variable for looping.

Conclusion

The brute force approach is simple and works for small arrays, but it’s too slow for large inputs.

Optimal Solution (Binary Search with Duplicates Handling)

Intuition and Approach

We can do much better using a modified binary search:

1. Binary Search:
   Use two pointers (low and high) to perform binary search.
2. Handle Duplicates:
   If nums[low], nums[mid], and nums[high] are all equal, we can’t decide which half is sorted, so we shrink the search window from both ends.
3. Check Sorted Halves:
   • If the left half is sorted, check if the target is in the left half.
   • If not, check the right half.
4. Why does this work?
   Binary search is efficient, and by handling duplicates, we avoid getting stuck in ambiguous situations.

Code Implementation

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

        while low <= high:
            mid = (low + high) // 2              # Find the middle index

            if nums[mid] == target:              # If middle element is target, return True
                return True

            # If we encounter duplicates making it unclear which side is sorted
            if nums[low] == nums[mid] == nums[high]:
                high -= 1
                low += 1
                continue

            # Check if left half is sorted
            if nums[low] <= nums[mid]:
                # Target lies in the left half
                if nums[low] <= target <= nums[mid]:
                    high = mid - 1               # Move to the left half
                else:
                    low = mid + 1                # Move to the right half
            # Else, right half is sorted
            else:
                # Target lies in the right half
                if nums[mid] <= target <= nums[high]:
                    low = mid + 1                # Move to the right half
                else:
                    high = mid - 1               # Move to the left half

        return False                             # Target not found

Code Explanation

• We use binary search with pointers low and high.
• If we find the target at mid, return True.
• If duplicates at both ends and middle, shrink the window.
• If the left half is sorted, check if the target is in it.
• Otherwise, check the right half.
• If not found, return False.

Dry Run

Input:
nums = [1], target = 0

• low = 0, high = 6
• mid = 3, nums = 0 (target found!)
• Return True

Input:
nums = [1], target = 3

• low = 0, high = 6
• mid = 3, nums = 0
• Left half is not sorted, right half is sorted.
• 3 not in right half, move high to mid – 1.
• Continue until low > high.
• Return False

Time and Space Complexity

• Time Complexity: O(log n) in the best case, but O(n) in the worst case (when there are many duplicates).
• Space Complexity: O(1)
  Only a few pointers are used.

Conclusion

The optimal solution is efficient and handles duplicates gracefully. It’s the best approach for interviews and large datasets.

Final Thoughts

The “Search in Rotated Sorted Array II” problem is a great example of how to adapt binary search for tricky cases, like duplicates. Start with brute force to understand the basics, then use the optimal solution for best performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.