33. 搜索旋转排序数组

关键思路

1. 使用二分查找
2. 判断有序区间，t > nums[end] 左边是有序的，t <= nums[end] 右边是有序的
3. 判断目标值 target，在有序区间还是非有序区间

题目

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

提示：

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -104 <= target <= 104

解题思路

这道题目要求在旋转后的有序数组中查找目标值。旋转后的有序数组是指一个原本有序的数组在某个点进行了旋转，例如 [4, 5, 6, 7, 0, 1, 2] 是由 [0, 1, 2, 4, 5, 6, 7] 旋转得到的。我们需要在这样的数组中高效地查找目标值。

1. 理解问题

• 输入：一个旋转后的有序数组 nums 和一个目标值 target。

• 输出：目标值在数组中的索引，如果不存在则返回 -1。

2. 分析数组特点

旋转后的数组虽然整体不是有序的，但它可以被分为两个部分，每一部分都是有序的。例如，[4, 5, 6, 7, 0, 1, 2] 可以分为 [4, 5, 6, 7] 和 [0, 1, 2]，这两部分都是有序的。

3. 二分查找的适用性

二分查找通常用于有序数组，但在这里我们可以利用旋转数组的部分有序性来应用二分查找。关键在于如何判断目标值位于哪一部分。

4. 算法步骤

• 初始化：设置两个指针 start 和 end，分别指向数组的起始和末尾。

• 循环条件：当 start <= end 时，继续查找。

• 中间值：计算中间索引 i = (start + end) // 2，并获取中间值 t = nums[i]。

• 判断中间值：

  • 如果 t == target，直接返回 i。

  • 如果 t > nums[end]，说明左半部分是有序。此时如果 nums[start] <= target < t，则目标值在左半部分，否则在右半部分。

  • 如果 t <= nums[end]，说明右半部分是有序。此时如果 t < target <= nums[end]，则目标值在右半部分，否则在左半部分。

• 更新指针：根据上述判断，更新 start 或 end 指针，缩小查找范围。

• 返回结果：如果循环结束仍未找到目标值，返回 -1。

5. 代码实现

# 二分查找
# https://leetcode.cn/problems/search-in-rotated-sorted-array
from typing import Listclass Solution:def search(self, nums: List[int], target: int) -> int:start = 0end = len(nums) - 1while start <= end:i = (start + end) // 2t = nums[i]if t == target:return iif t > nums[end]:# 当 t > nums[end]时，且 nums[start] <= target < t  左边元素一定是顺序if nums[start] <= target < t:end = i - 1else:start = i + 1else:# 当 t < nums[end]时，且 t < target <= nums[end] 右边元素一定是顺序if t < target <= nums[end]:start = i + 1else:end = i - 1return -1if __name__ == '__main__':s = Solution()r = s.search([4, 5, 6, 7, 0, 1, 2], 0)print(r)r = s.search([4, 5, 6, 7, 0, 1, 2], 3)print(r)r = s.search([1], 0)print(r)r = s.search([1, 3], 0)print(r)r = s.search([5, 1, 3], 5)print(r)r = s.search([1, 3], 3)print(r)r = s.search([3, 5, 1], 3)print(r)r = s.search([4, 5, 6, 7, 8, 1, 2, 3], 8)print(r)r = s.search([5, 1, 3], 3)print(r)