81_Search in Rotated Sorted Array II
81. Search in Rotated Sorted Array II
Level: medium
Tag: array, binary search
Question
follow up of Q33 Search in Rotated Sorted Array
What if duplicates are allowed? Would this affect the run-time complexity? How and why?
Example 1
Idea (binary search)
Use the algorithm for Q33. Add one more test to avoid conner cases like example 1. Bad thing about example 1 is that when middle point is third integer, either half is sorted. We can further check if middle integer is the same as left and right. If yes, move left and right one step further.
Complexity
Time:
Space:
Solution
Last updated