Search in Rotated Sorted Array II
mediumTime: O(log n)Space: O(1)
Signals to notice
rotated sorted array with duplicatesfind targetworst case O(n)
Brute force first
Linear scan — O(n).
The key insight
Modified binary search: when left == mid == right, shrink both ends. Otherwise, standard rotated array logic. Average O(log n), worst O(n).
What must stay true
Duplicates prevent determining which half is sorted when left == mid == right. Shrinking by one is the only safe option.
Easy way to go wrong
Not handling the ambiguous case — without it, you eliminate the wrong half.