搜索旋转排序数组

33. 搜索旋转排序数组 - 力扣（LeetCode）

问题简述

在一个旋转过的有序数组中搜索某值，若存在返回下标，否则返回 -1。
进阶：时间复杂度要求 O(log n)

思路

• “二分”的本质是两段性，而不是单调性；即只要二分后，左边满足某个性质，右边不满足某个性质，即可使用二分；

  LogicStack-LeetCode/33.搜索旋转排序数组（中等）

• 本题中，将数组从中间分开后，其中一个部分一定是有序的:

  • 有序部分可以通过比较 a[m] 和 a[0] 得到；

  • 此时如果 target 在有序部分，那么可以排除无序的一半，否则可以排除有序的一半；

• 细节详见代码；

Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:

        l, r = 0, len(nums)  # [l, r) 左闭右开区间
        while l < r:
            m = l + (r - l) // 2

            if nums[m] == target: 
                return m
            
            if nums[0] < nums[m]:
                # 此时 m 左边是有序的
                if nums[l] <= target < nums[m]:
                    # 如果 target 在有序部分, 即在左侧
                    r = m
                else:
                    l = m + 1
            else:
                # 此时 m 右边是有序的
                if nums[m] < target <= nums[r - 1]:  # r 是开区间, 所以 - 1
                    # 如果 target 在有序部分, 此时在右侧
                    l = m + 1
                else:
                    r = m  # 右边界

        return -1