Search in Rotated Sorted Array II
mediumTime: O(log n)Space: O(1)
Recognize the pattern
rotated sorted array with duplicatesfind targetworst case O(n)
Brute force idea
Linear scan — O(n).
Better approach
Modified binary search: when left == mid == right, shrink both ends. Otherwise, standard rotated array logic. Average O(log n), worst O(n).
Key invariant
Duplicates prevent determining which half is sorted when left == mid == right. Shrinking by one is the only safe option.
Watch out for
Not handling the ambiguous case — without it, you eliminate the wrong half.