1 中文题目

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

在传递给函数之前，$nums$ 在预先未知的某个下标 $k（0\le 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(logn)$ 的算法解决此问题。

示例：

输入：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

提示：

• $1\le nums.length\le 5000$
• $-10^4\le nums[i]\le 10^4$
• $nums$ 中的每个值都 独一无二
• 题目数据保证 $nums$ 在预先未知的某个下标上进行了旋转
• $-10^4\le target\le 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 = 6mid = 3, nums[mid] = 72. 第一次迭代：nums[left] <= nums[mid]：左半部分有序target不在[4,7]内left = mid + 1 = 43. 第二次迭代：left = 4, right = 6mid = 5, nums[mid] = 1nums[left] > nums[mid]：右半部分有序target在[0,1]内right = mid - 1 = 44. 第三次迭代：left = 4, right = 4mid = 4, nums[mid] = 0找到目标值返回：4

2.2 Python代码

class Solution:def search(self, nums: List[int], target: int) -> int:if not nums:return -1left, right = 0, len(nums) - 1while 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 - 1return -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

• 时间复杂度：O(n)
  • in 操作需要O(n)时间
  • index()方法需要O(n)时间

没有利用题目中的数组是有序的特点，也没有利用数组只经过一次旋转的特点

---

3 题目总结

题目难度：中等
数据结构：数组
应用算法：二分查找