[Leetcode][python]搜索旋转排序数组/搜索旋转排序数组 II

蔚落 2022-06-09 14:54 260阅读 0赞

# Search in Rotated Sorted Array #

## 题目大意 ##

把一个严格升序的数组进行旋转，如\[0,1,2,3,4,5\]旋转3位成为\[3,4,5,0,1,2\]。在这样的数组中找到目标数字。如果存在返回下标，不存在返回-1。  
输入: nums = \[4, 5, 6, 7, 0, 1, 2\], target = 6 输出: 2  
输入: nums = \[4, 5, 6, 7, 0, 1, 2\], target = 3 输出: -1

## 解题思路 ##

二分搜索是针对有序数组而言，对于中间有次转折的有序数组，只是要多区分几种情况，二分搜索依然是适用的。  
主要就是判断mid的左右哪边是中断的

## 代码 ##

**该解法的判断表达是对称的结构，有助于记忆**

class Solution(object):
        def search(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            left = 0; right = len(nums) - 1
            while left <= right:
                mid = (left + right) / 2
                if target == nums[mid]:
                    return mid
                if nums[mid] >= nums[left]:  # 中点大于最左边，说明左边区间没有混乱
                    if target < nums[mid] and target >= nums[left]:  # 此时若目标数小于中间数而且大于最左边，说明就在左边区间
                        right = mid - 1
                    else:  # 不然就在右边区间
                        left = mid + 1
                else:  # 中点小于最右边，说明右边区间没有混乱
                    if target > nums[mid] and target <= nums[right]:  # 此时若目标数大于中间数而且小于最右边，说明就在右边区间
                        left = mid + 1
                    else:  # 不然就在左边区间
                        right = mid - 1
            return -1  # 找不到

# Search in Rotated Sorted Array II #

## 题目大意 ##

把一个有重复的排序数组进行旋转，如\[0,1,1,1,2,3,4,5\]旋转3位成为\[3,4,5,0,1,1,1,2\]。在这样的数组中判断目标数字是否存在。

## 解题思路 ##

和上题其实唯一的区别在于如果重复的数字中间进行了旋转，所以只要加入

if nums[left] == nums[mid] == nums[right]:
        left += 1
        right -= 1

其他相同。

## 代码 ##

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[left] == nums[mid] == nums[right]:  # 所有指针都一个数字，说明旋转时有的在左边有的在右边，需要往中间看
                    left += 1
                    right -= 1
                elif nums[mid] >= nums[left]:  # 中点大于最左边，说明左边区间没有混乱
                    if target < nums[mid] and target >= nums[left]:  # 此时若目标数小于中间数而且大于最左边，说明就在左边区间
                        right = mid - 1
                    else:  # 不然就在右边区间
                        left = mid + 1
                else:  # 中点小于最右边，说明右边区间没有混乱
                    if target > nums[mid] and target <= nums[right]:  # 此时若目标数大于中间数而且小于最右边，说明就在右边区间
                        left = mid + 1
                    else:  # 不然就在左边区间
                        right = mid - 1
            return False

## 总结 ##