81. 搜索旋转排序数组 II(Medium)

题目描述

一个原本增序的数组被首尾相连后按某个位置断开（如 [1,2,2,3,4,5] → [2,3,4,5,1,2]，在第一 位和第二位断开），我们称其为旋转数组。给定一个值，判断这个值是否存在于这个为旋转数组中。

样例

Input: [2,5,6,0,0,1,2], 0
Output: true

Input: [2,5,6,0,0,1,2], 3
Output: false

题解

本题的难点在于，如何应对重复元素，通常 的做法是 left += 1 或 right -= 1搜小范围

Python示例

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