当前位置：首页 > article >正文

LeetCode【0033】搜索旋转排序数组

article 2024/11/14 7:04:32

本文目录

1 中文题目
2 求解方法：二分查找
- 2.1 方法思路
- 2.2 Python代码
- 2.3 复杂度分析
- 2.4 不可以的投机取巧法
3 题目总结

1 中文题目

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

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

给定 旋转后 的数组 $n u m s$ 和一个整数 $t a r g e t$ ，如果 $n u m s$ 中存在这个目标值 $t a r g e t$ ，则返回它的下标，否则返回 $- 1$ 。

注意：必须设计一个时间复杂度为 $O (l o g n)$ 的算法解决此问题。

示例：

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

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

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

提示：

$\leq nums.length \leq 5000$
$-10^4 \leq nums[i] \leq 10^4$
$n u m s$ 中的每个值都 独一无二
题目数据保证 $n u m s$ 在预先未知的某个下标上进行了旋转
$-10^4 \leq target \leq 10^4$

2 求解方法：二分查找

2.1 方法思路

方法核心

使用改进的二分查找
根据有序部分的位置判断搜索区间
利用旋转数组的特性进行查找

实现步骤

（1）初始化：

设置双指针left和right
处理空数组特殊情况

（2）二分查找：

计算中间位置
判断mid位置的值

（3）区间判断：

判断哪半部分是有序的
确定目标值可能在的区间

方法示例

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

过程演示：
1. 初始状态：
   left = 0, right = 6
   mid = 3, nums[mid] = 7

2. 第一次迭代：
   nums[left] <= nums[mid]：左半部分有序
   target不在[4,7]内
   left = mid + 1 = 4

3. 第二次迭代：
   left = 4, right = 6
   mid = 5, nums[mid] = 1
   nums[left] > nums[mid]：右半部分有序
   target在[0,1]内
   right = mid - 1 = 4

4. 第三次迭代：
   left = 4, right = 4
   mid = 4, nums[mid] = 0
   找到目标值

返回：4

2.2 Python代码

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
            
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            # 如果找到目标值，直接返回
            if nums[mid] == target:
                return mid
                
            # 判断左半部分是否有序
            if nums[left] <= nums[mid]:
                # 如果目标值在左半有序部分
                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

2.3 复杂度分析

时间复杂度：O(log n)
- 每次迭代将搜索范围减半
- 典型的二分查找复杂度
空间复杂度：O(1)
- 只使用常数额外空间

2.4 不可以的投机取巧法

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if target in nums:
            return nums.index(target)
        else:
            return -1