【二分查找-1】33.搜索旋转排序数组

题目描述：

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

解题思路：

方法：二分查找

核心思路：

旋转后的数组，从中间切开，至少有一半是有序的：

[4, 5, 6, 7, 0, 1, 2] ↑ mid=3 左半部分 [4, 5, 6, 7] 有序 右半部分 [0, 1, 2] 有序

判断哪一半有序，然后看 target 是否在有序的那一半中。

算法步骤：

1. 计算mid

2. 如果nums[mid] == target，返回mid

3. 判断左半部分是否有序：nums[left] <= nums[mid]

   • 如果左半部分有序：

     • 如果nums[left] <= target < nums[mid]，在左半部分找 →right = mid - 1

     • 否则在右半部分找 →left = mid + 1

   • 如果右半部分有序：

     • 如果nums[mid] < target <= nums[right]，在右半部分找 →left = mid + 1

     • 否则在左半部分找 →right = mid - 1

具体过程示例：

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

初始: left=0, right=6, mid=3 [4, 5, 6, 7, 0, 1, 2] ↑ ↑ ↑ left mid right nums[mid]=7 != 0 nums[left]=4 <= nums[mid]=7 → 左半部分有序 target=0 不在 [4, 7) 中 → 在右半部分找 left = mid+1 = 4 left=4, right=6, mid=5 [4, 5, 6, 7, 0, 1, 2] ↑ ↑ ↑ left mid right nums[mid]=1 != 0 nums[left]=0 <= nums[mid]=1 → 左半部分有序 target=0 在 [0, 1) 中 → 在左半部分找 right = mid-1 = 4 left=4, right=4, mid=4 nums[mid]=0 == target → 返回 4 ✅

代码实现：

class Solution { public: int search(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } // 判断左半部分是否有序 if (nums[left] <= nums[mid]) { // 左半部分有序 if (nums[left] <= target && target < nums[mid]) { right = mid - 1; // target 在左半部分 } else { left = mid + 1; // target 在右半部分 } } else { // 右半部分有序 if (nums[mid] < target && target <= nums[right]) { left = mid + 1; // target 在右半部分 } else { right = mid - 1; // target 在左半部分 } } } return -1; } };

复杂度分析：

关键细节：

1. 为什么用nums[left] <= nums[mid]判断左半部分有序？

• 如果nums[left] <= nums[mid]，说明左半部分没有旋转点，是有序的

• 否则，旋转点在左半部分，右半部分有序

2. 为什么用<=而不是<？

因为nums[mid]可能等于nums[left]（比如left == mid时），用<=更安全。

3. 边界条件

if (nums[left] <= target && target < nums[mid])

• target < nums[mid]不是<=，因为nums[mid] == target已经在前面判断过了

• nums[left] <= target是<=，因为nums[left]可能就是 target

4. 和「搜索旋转排序数组 II」的区别

81 题需要额外处理nums[left] == nums[mid] == nums[right]的情况。

总结：