[LeetCode]81 搜索旋转排序数组II

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

示例1:

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true

示例2:

输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        left,right=0,len(nums)-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]==target:
                return True
            
            if nums[mid]<nums[right]:
                if target>nums[mid] and target<=nums[right]:
                    left=mid+1
                else:
                    right=mid-1
                
            elif nums[mid]>nums[right]:
                if target<nums[mid] and target>=nums[left]:
                    right=mid-1
                else:
                    left=mid+1
            else:
                right=right-1
                    
        return False