[leetcode]@python 81. Search in Rotated Sorted Array II

题目链接

https://leetcode.com/problems/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?

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

题目大意

接Search in Rotated Sorted Array,如果允许重复,这会影响时间复杂度么，how and why,给定target，判断它是否在数组中

解题思路

有重复的话，多了一个判断条件就是三点相等时，左右端点同时变化,影响就是，如果在重复中间截断逆转，之后再用 nums[start]<=target<nums[mid] 去判断，就找不到这个target

代码

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left+right)//2
            if nums[mid]==target:
                return True
            if nums[mid]==nums[left]==nums[right]:
                left += 1
                right -= 1
            elif nums[left] <= nums[mid]:
                if nums[left] <= target and target < nums[mid]:
                    right = mid -1
                else:
                    left = mid + 1
            else:
                if nums[mid] <= target and target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid -1
        return False