There is an integer array nums sorted in non-decreasing order (possibly with duplicates), which is possibly rotated at an unknown pivot index k. Given nums and an integer target, return true if target is in nums, or false if it is not. The key difference from LC #33: duplicates are allowed, making the "SKIP DUPS" case necessary when nums[lo]==nums[mid]==nums[hi].
nums = [2,5,6,0,0,1,2], target = 0truenums = [2,5,6,0,0,1,2], target = 3falsenums = [1,0,1,1,1], target = 0truelo=0, hi=n-1. Loop while lo <= hi, compute mid.nums[mid]==target: return true.nums[lo]==nums[mid]==nums[hi] → ambiguous, do lo++; hi--.nums[lo]<=nums[mid]: left half sorted → search or discard left.false.
In LC #33 (no duplicates), nums[lo] <= nums[mid] reliably means the left half is sorted. But with duplicates, nums[lo]==nums[mid]==nums[hi] is possible — we literally cannot tell which side the rotation pivot is on, so neither half can be confidently declared sorted.
The fix is simple but powerful: increment lo and decrement hi to skip one known duplicate on each end. This degrades worst-case to O(n) (e.g., [1,1,1,1,1]) but preserves O(log n) average behaviour on random inputs.
The approach from problem 33 compares the value at low with the value at mid to find the sorted half. With duplicates, they can be equal, and then you cannot tell which half is sorted.
Use the same idea as problem 33. But if the values at low, mid and high are all equal, you learn nothing. In that case, shrink both ends by one and try again.
Duplicates can hide the sorted half. When low, mid and high are equal, shrink both ends.
Run the animation above on your own input, or watch the 1:15 video explanation of Search in Rotated Sorted Array II with a dry run and Java code.