[LeetCode]Search in Rotated Sorted Array II

有duplicate的情况，duplicate造成的问题就是这个时候我们没办法区分那一边是sorted的。
对于递归的版本来说，我们就只能去两边一起找，只要一边有的话就返回true。Worst case：T(N) = 2 * T(N/2) + 1，根据Master Theorem, 时间复杂度是O(N)。

代码如下：



对于迭代的版本来说, 当我们没办法判断[mid,hi]区间是不是sorted的时候，我们只能排除hi位置的数字，所以只需要--hi即可，剩下的还是一样。最坏的情况也是O(N)。

代码如下：