[Leetcode Solution] Search in Rotated Sorted Array II

Analysis

• Almost the same as Search in Rotated Sorted Array
• The only difference resulting from the duplicates is we cannot judge if a sequence is rotated by compare the first and last element of the sequence.
• So the solution is when the first and last elements are the same, we just move backward of the first index, and do recursively.
• So the complexity of the worst case is O(n) now 

Note

Code