Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).

Write a function to determine if a given target is in the array.

The array may contain duplicates.3

这道是之前那道Search in Rotated Sorted Array 在旋转有序数组中搜索的延伸，现在数组中允许出现重复数字，这个也会影响我们选择哪半边继续搜索，由于之前那道题不存在相同值，我们在比较中间值和最右值时就完全符合之前所说的规律：如果中间的数小于最右边的数，则右半段是有序的，若中间数大于最右边数，则左半段是有序的。而如果可以有重复值，就会出现来面两种情况，[3 1 1] 和 [1 1 3 1]，对于这两种情况中间值等于最右值时，目标值3既可以在左边又可以在右边，我们无法判断哪边是有序的，那怎么办？对于这种情况其实处理非常简单，只要把最右值向左一位即可继续循环，如果还相同则继续移，直到移到不同值为止，然后其他部分还采用 Search in Rotated Sorted Array 在旋转有序数组中搜索中的方法

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        if len(nums)==0:
            return False
        start, end = 0, len(nums)-1
        while start + 1 < end:
            mid = (start + end)/2
            if nums[mid] == nums[end]:
                end -= 1
            # 右边是有序
            elif nums[mid] < nums[end]:
                if target < nums[mid] or target > nums[end]:
                    end = mid
                else:
                    start = mid
            # 左边有序
            else:
                if target > nums[mid] or target < nums[start]:
                    start = mid
                else:
                    end = mid
        if nums[start] == target or nums[end] == target:
            return True
        else:
            return False