⚡Flashcard Drill➔
NeetCode #286LC-81MediumBinary SearchNC 250
← Back to All Problems

#286 · #81 · Search in Rotated Sorted Array II(搜索旋转排序数组 II)

📌 Problem Statement & Constraints

Given a rotated sorted array nums that may contain duplicates, and a target, return whether the target exists in the array. Constraints: 1 <= nums.length <= 5000, -10^4 <= nums[i], target <= 10^4. The follow-up asks whether the algorithm can still be O(log n).

💡 Core Algorithmic Approaches

  1. The same sorted-half test as in the distinct version, with one extra case.
  2. When nums[lo] == nums[mid] == nums[hi], the sorted half cannot be identified, so shrink both ends by one and retry.
  3. That fallback is what makes the worst case O(n) -- for example, an array of all equal values with one different element forces many shrinks.
  4. So the honest answer to the follow-up is: O(log n) is not achievable in the worst case when duplicates are allowed.

💻 Benchmark Python3 Implementation

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return True
            if nums[lo] == nums[mid] == nums[hi]:
                # cannot tell which half is sorted -> shrink both ends
                lo += 1
                hi -= 1
                continue
            if nums[lo] <= nums[mid]:          # left half sorted
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:                              # right half sorted
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return False

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n) on average, but O(n) in the worst case because of the duplicate-shrinking fallback.
💾 Space Complexity
O(1): three indices.

⚠️ Interview Pitfalls & Follow-ups

  • Claiming O(log n) worst case: with duplicates it is not achievable; be honest about the O(n) worst case.
  • Omitting the three-way equality check: the sorted-half test would be ambiguous and the algorithm would return wrong results.
  • Using nums[lo] < nums[mid]: with duplicates the strict comparison misclassifies single-element subarrays.
  • Shrinking only one end in the ambiguous case: both must shrink, otherwise progress can stall.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems