# Search in Rotated Sorted Array II

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.

Example

```
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).