在旋转过的有序数组中寻找目标值

在旋转过的有序数组中寻找目标值_牛客题霸_牛客网

问题简述

有一个长度为 n 的按严格升序排列的整数数组 nums ，在实行 search 函数之前，在某个下标 k 上进行旋转；
给定旋转后的数组 nums 和一个整型 target ，请你查找 target 是否存在于 nums 数组中并返回其下标（从0开始计数），如果不存在请返回-1。

思路

• 通过比较 nums[m] 和 nums[0] 可以得到知道当前哪部分是有序的；

  • 比如当 nums[m] > nums[0] 时，[l, m] 是有序的，反之 [m, r] 是有序的；

• 然后看 target 是否在有序部分内，然后确定下一步的搜索区间；

写法1：[l, r] 闭区间

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        
        l, r = 0, len(nums) - 1  # 闭区间
        
        # 中止条件：区间内没有元素，对闭区间来说，就是 l > r
        while l <= r:
            m = (l + r) // 2

            if nums[m] == target:
                return m
            
            # 因为 nums 严格递增，可以不考虑等于的情况
            if nums[m] > nums[0]:
                # [l, m] 有序
                if nums[l] <= target < nums[m]:  # 注意 target 可能 == nums[l]
                    r = m - 1
                else:
                    l = m + 1
            else:
                # [m, r] 有序
                if nums[m] < target <= nums[r]:  # 同理 target 是可能 == nums[r]
                    l = m + 1
                else:
                    r = m - 1
            # 因为是闭区间，所以当端点明确不可能是 target 时，可以置信的 +1 或 -1
        
        return -1

写法2：[l, r) 左闭右开

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        
        l, r = 0, len(nums)  # [l, r) 左闭右开
        
        # 中止条件：区间内没有元素，对半开区间来说，就是 l >= r
        while l < r:  # !
            m = (l + r) // 2

            if nums[m] == target:
                return m
            
            if nums[m] > nums[0]:
                if nums[l] <= target < nums[m]:
                    r = m  # !
                else:
                    l = m + 1
            else:
                if nums[m] < target <= nums[r - 1]:  # 防止越界
                    l = m + 1
                else:
                    r = m  # !
        
        return -1

写法3：(l, r] 左开右闭

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        
        l, r = -1, len(nums) - 1  # (l, r] 左开右闭
        
        # 中止条件：区间内没有元素，对半开区间来说，就是 l >= r
        while l < r:  # !
            m = (l + r + 1) // 2  # +1 保证取到中间值

            if nums[m] == target:
                return m
            
            if nums[m] > nums[0]:
                if nums[l + 1] <= target < nums[m]:  # 防止越界
                    r = m - 1
                else:
                    l = m  # !
            else:
                if nums[m] < target <= nums[r]:
                    l = m  # !
                else:
                    r = m - 1
        
        return -1