day127—二分查找—搜索旋转排序数组（LeetCode-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

提示：

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

解决方案：

核心逻辑

代码利用旋转数组「被最小值拆分为两个独立升序子数组」的特性，把复杂的旋转数组查找拆解为两步：

1. 找分割点：通过findMin函数用二分法找到数组最小值的索引（即两个升序子数组的分割点）；
2. 分区间查找：根据target与数组最后一个元素的大小关系，判断target属于左侧还是右侧升序子数组，再通过lower_bound函数在对应有序区间内用二分法查找目标值，最终返回结果。

总结

1. 核心策略：将旋转数组查找拆解为「找分割点 + 有序区间二分」，把无序问题转化为有序问题解决；
2. 关键设计：全程使用开区间二分法（循环条件left + 1 < right），简化边界处理，避免越界；
3. 效率保障：两次二分查找均为O(log n)，整体保持对数级时间复杂度，高效且稳定。

函数源码：

class Solution { int findMin(vector<int>& nums) { int left = -1, right = nums.size() - 1; // 开区间 (-1, n-1) while (left + 1 < right) { // 开区间不为空 int mid = left + (right - left) / 2; if (nums[mid] < nums.back()) { right = mid; } else { left = mid; } } return right; } // 有序数组中找 target 的下标 int lower_bound(vector<int>& nums, int left, int right, int target) { while (left + 1 < right) { // 开区间不为空 // 循环不变量： // nums[right] >= target // nums[left] < target int mid = left + (right - left) / 2; if (nums[mid] >= target) { right = mid; // 范围缩小到 (left, mid) } else { left = mid; // 范围缩小到 (mid, right) } } return nums[right] == target ? right : -1; } public: int search(vector<int>& nums, int target) { int i = findMin(nums); if (target > nums.back()) { // target 在第一段 return lower_bound(nums, -1, i, target); // 开区间 (-1, i) } // target 在第二段 return lower_bound(nums, i - 1, nums.size(), target); // 开区间 (i-1, n) } };