81. Search in Rotated Sorted Array II.md

81. Search in Rotated Sorted Array II

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

solution

• 存在重复值
• 返回的值是否存在

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        if not nums:
            return False
        
        l = 0
        r = len(nums) - 1

        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] == target:
                return True
            
            if nums[mid] == nums[l]: # Fail to estimate which side is sorted, if的这一环节一开始没想到
                l += 1  # In worst case here: O(n)
            
            elif nums[mid] > nums[l]:
                if nums[mid] > target >= nums[l]:
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
        return False

时间复杂度：O(n)
空间复杂度：O(1)