LeetCode 33. Search in Rotated Sorted Array 题解题目描述整数数组nums按升序排列数组中的值互不相同。在传递给函数之前nums在预先未知的某个下标k0 k nums.length上进行了旋转使数组变为[nums[k], nums[k1], ..., 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解题思路方法二分查找思路由于数组是旋转排序的所以数组可以分为两部分每部分都是升序的且前一部分的所有元素都大于后一部分的所有元素。我们可以使用二分查找来快速定位目标值。具体步骤初始化左指针left为 0右指针right为数组长度减 1。当left right时计算中间位置mid。如果nums[mid] target返回mid。确定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。如果循环结束仍未找到目标值返回-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)适用于大规模旋转排序数组的查找。掌握二分查找的原理对于理解搜索算法和算法设计思想非常重要。