Missing Test Case - 81. Search in Rotated Sorted Array II #31063
Description
LeetCode Username
CodeSlayer
Problem Number, Title, and Link
- Search in Rotated Sorted Array II https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
Bug Category
Missing test case (Incorrect/Inefficient Code getting accepted because of missing test cases)
Bug Description
Missing test case / incomplete test coverage
The current official test cases for problem #81 do not cover cases where duplicates cause ambiguity in the binary search, allowing incorrect solutions to be accepted.
For example, the input:
nums = [1, 0, 1, 1, 1]
target = 0
should return True, but some accepted solutions that do not handle duplicates correctly fail on this input.
Language Used for Code
Python/Python3
Code used for Submit/Run operation
class Solution(object):
def search(self, nums, target):
l = 0
h = len(nums) - 1
while l <= h:
m = (l + h) // 2
if nums[m] == target:
return True
elif nums[l] <= nums[m]:
if nums[l] <= target < nums[m]:
h = m - 1
else:
l = m + 1
else:
if nums[m] < target <= nums[h]:
l = m + 1
else:
h = m - 1
return FalseExpected behavior
The input nums = [1, 0, 1, 1, 1], target = 0 should return True.
Currently, the problem does not test for this case, allowing incorrect solutions to be accepted.
Adding this test case will improve problem coverage and help ensure solutions handle duplicates properly.
Screenshots
No response
Additional context
This test case is important because duplicates can cause ambiguity in determining which half of the array is sorted. Proper handling requires shrinking the search bounds when nums[l] == nums[m] == nums[h].