python -- leetcode ---- 81.Search in Rotated Sorted Array II

红太狼 2022-05-13 13:44 131阅读 0赞

### \-81.Search in Rotated Sorted Array II ###

给定一个list,是由一个有序数组在某一枢纽处旋转得到的,并且其中可能含有重复元素,要求判断target是否在这个list中.

虽然这个list经过旋转,但是还是可以用二分查找的思想,因为mid的左边或右边一定有一端是有序的.因此只需要在二分查找的时候对此进行判断就行了.另外本题可能有重复值,所以当left,mid和right指向的值都相等时要移动指针来跳出循环.

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

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

[ExpandedBlockStart.gif]: /images/20220504/52e68468550b4696b67689fe44feeef4.png
[copycode.gif]: /images/20220504/42955428e28b4633ab4724790426e4cc.png