↓Skip to main content
  1. Posts/

LeetCode-81 搜索旋转排序数组 II

·2 mins·
Table of Contents

LeetCode-81 搜索旋转排序数组 II #

Solution 1 #

允许重复元素的旋转数组二分查找, 重要的是理解重复元素的处理.

代码如下:

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        n = len(nums)
        l, r = 0, n - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[l] < nums[mid]:
                if nums[l] <= target <= nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            elif nums[l] > nums[mid]:
                if nums[l] <= target or nums[mid] >= target:
                    r = mid -1 
                else:
                    l = mid + 1
            else:
                if nums[l] != target:
                    l += 1
                else:
                    return True
        if l < n and nums[l] == target:
            return True
        return False

补充: 面试题 10.03. 搜索旋转数组 #

要求输出下标, 类似.

代码如下:

class Solution:
    def search(self, arr: List[int], target: int) -> int:
        n = len(arr)
        l, r = 0, n - 1
        while l <= r:
            mid = (l + r) // 2
            if arr[l] < arr[mid]: 
                if arr[l] <= target <= arr[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            elif arr[l] > arr[mid]: 
                if arr[l] <= target or arr[mid] >= target:
                    r = mid - 1
                else: 
                    l = mid + 1
            else: 
                if arr[l] != target:
                    l = l + 1 
                else:
                    break
        if l < n and arr[l] == target:
            return l
        return -1
↑