蓝桥杯每日一练--搜索旋转排序数组

目录

一、题目

二、分析

三、代码

一、题目

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

输入：nums = [1], target = 0
输出：-1

二、分析

我看到这道题的第一想法就是暴力求解，挨个遍历，但很不幸题目中要求了时间复杂度为 O(log n)，因此该方法排除。其次，注意到logn的时间复杂度之后，我又想到了二分查找，但二分查找的前提在于要求数组有序排列，所以，我下意识地想到了先将该数组重整为有序数组，然后再使用二分查找，但是想将该数组重新排序，又要用的for循环，那么时间复杂度又将不符合题意。所以我意识到这道题是不是能直接使用二分查找来求解。在仔细分析题干之后，我总结出了解题思路：

1. 将数组一分为二。（其中有一个一定是有序的；另一个则是无序或部分有序的）
    
2. 此时如果target在有序部分里，则用二分法查找。
    
3. 否则进入无序部分查找，继续二分。

总的来说就是一直二分查找，我们要做的就是控制好指针的变化即可。

三、代码

具体代码如下

def search(nums,target):
    left=0
    right=len(nums)-1
    while left<=right:
        mid=(left+right)//2
        if target==nums[mid]:
            return mid
        if nums[mid]>=nums[right]:
            if nums[left]<=target<=nums[mid]:
                right=mid-1
            else:
                left=mid+1
        else:
            if nums[mid]<=target<=nums[right]:
                left=mid+1
            else:
                right=mid-1
    return -1

nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
print(search(nums, target))
target = 3
print(search(nums, target))
nums = [1]
target = 0
print(search(nums, target))

1. 首先初始化两个指针 left 和 right 分别指向数组的首尾位置。
2. 进入循环，只要 left 不超过 right，就继续循环。
   • 计算中间索引 mid。
   • 如果中间元素等于目标值，直接返回中间索引。
   • 然后判断哪一部分是有序的：
     • 如果左半部分有序，并且目标值在左半部分范围内（大于等于 nums[left] 且小于 nums[mid]），说明目标值在左半部分，将 right 更新为 mid - 1。
     • 否则目标值在右半部分，将 left 更新为 mid + 1。
   • 如果左半部分无序，说明右半部分有序：
     • 如果目标值在右半部分范围内（大于等于 nums[mid] 且小于等于 nums[right]），说明目标值在右半部分，将 left 更新为 mid + 1。
     • 否则目标值在左半部分，将 right 更新为 mid - 1。
3. 如果循环结束还没有找到目标值，返回 -1。