↓Skip to main content
  1. Posts/

LeetCode-33 搜索旋转排序数组

·1 min·
Table of Contents

LeetCode-33 搜索旋转排序数组 #

Solution 1 #

数组分段有序, 但依然可以使用二分缩小范围. 注意细节, 分类讨论需要考虑清楚. 代码如下:

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