LeetCode 33. Search in Rotated Sorted Array 题解

LeetCode 33. Search in Rotated Sorted Array 题解

题目描述

整数数组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。

示例 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

解题思路

方法：二分查找

思路：

• 由于数组是旋转排序的，所以数组可以分为两部分，每部分都是升序的，且前一部分的所有元素都大于后一部分的所有元素。
• 我们可以使用二分查找来快速定位目标值。
• 具体步骤：
  1. 初始化左指针left为 0，右指针right为数组长度减 1。
  2. 当left <= right时，计算中间位置mid。
  3. 如果nums[mid] == target，返回mid。
  4. 确定mid所在的是左半部分还是右半部分：
     • 如果nums[left] <= nums[mid]，说明mid在左半部分：
       • 如果nums[left] <= target < nums[mid]，将right设为mid - 1。
       • 否则，将left设为mid + 1。
     • 否则，说明mid在右半部分：
       • 如果nums[mid] < target <= nums[right]，将left设为mid + 1。
       • 否则，将right设为mid - 1。
  5. 如果循环结束仍未找到目标值，返回-1。

复杂度分析：

• 时间复杂度：O(log n)，其中 n 是数组的长度。每次查找都会将查找区间减半。
• 空间复杂度：O(1)，只需要常数级的额外空间。

代码实现

方法：二分查找

class Solution: def search(self, nums: List[int], target: int) -> int: # 初始化左指针和右指针 left = 0 right = len(nums) - 1 # 当左指针小于等于右指针时，继续查找 while left <= right: # 计算中间位置 mid = left + (right - left) // 2 # 如果找到目标值，返回下标 if nums[mid] == target: return mid # 确定 mid 所在的是左半部分还是右半部分 if nums[left] <= nums[mid]: # mid 在左半部分 if nums[left] <= target < nums[mid]: # 目标值在左半部分，将右指针移到中间位置的左边 right = mid - 1 else: # 目标值在右半部分，将左指针移到中间位置的右边 left = mid + 1 else: # mid 在右半部分 if nums[mid] < target <= nums[right]: # 目标值在右半部分，将左指针移到中间位置的右边 left = mid + 1 else: # 目标值在左半部分，将右指针移到中间位置的左边 right = mid - 1 # 如果没有找到目标值，返回 -1 return -1

测试用例

测试用例 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)，适用于大规模旋转排序数组的查找。掌握二分查找的原理，对于理解搜索算法和算法设计思想非常重要。