This time the rotated array may contain duplicates. Return true if the target is present.
DSA Animator › DSA Revision › Binary Search › Search in Rotated Sorted Array II
Remember: duplicates can hide the sorted half. When low, mid and high are equal, shrink both ends. The video solves Search in Rotated Sorted Array II (LeetCode 81, Medium) with the Binary Search pattern from the Binary Search topic, and you can replay every step in the interactive Search in Rotated Sorted Array II animation.
This time the rotated array may contain duplicates. Return true if the target is present.
For 1, 0, 1, 1, 1 and target 0, the answer is true.
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.
Low 0, high 4, mid 2, and all three values are 1. So low becomes 1 and high becomes 3. Mid 2 holds 1, and the left part 0 to 1 is sorted and contains 0, so high becomes 1. Mid 1 holds 0, so the answer is true.
In code, return true on a match. If low, mid and high are equal, move both ends inward. Otherwise, use the sorted half logic from problem 33. It's O of log n on average, but O of n in the worst case, when almost everything is equal.
Remember: duplicates can hide the sorted half. When low, mid and high are equal, shrink both ends.