This is a follow up for Search in Rotated Sorted Array. Suppose a sorted array is rotated at some pivot unknown to you beforehand. You are given a target value to search. If found in the array return its index, otherwise return
-1. Duplicates are allowed in the array.
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
Array Target Return [1, 1, 0, 1, 1, 1] 0 true [1, 1, 1, 1, 1, 1] 0 false
The following algorithm uses binary search. The trick is that when
a[left] is equal to
a[right], we can discard one. In the following code, we discard
a[left]. The average time complexity is O(log n), but the worse case time complexity is O(n).