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
- The same sorted-half test as in the distinct version, with one extra case.
- When
nums[lo] == nums[mid] == nums[hi], the sorted half cannot be identified, so shrink both ends by one and retry. - 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.
- 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.