旋转排序数组二分查找解法：LeetCode 33 题实战

题目描述

整数数组 nums 原本按升序排列，但在传递给函数前，它在某个未知下标 k 处进行了旋转。

例如，[0,1,2,4,5,6,7] 在下标 3 处旋转后可能变为 [4,5,6,7,0,1,2]。

给定旋转后的数组 nums 和一个整数 target，如果 nums 中存在这个目标值，则返回它的下标，否则返回 -1。必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

解题思路

面对旋转后的有序数组，核心难点在于如何保持二分查找的 O(log n) 效率。由于数组被切断并拼接，整体不再单调，但局部依然有序。这意味着在任意一次二分迭代中，mid 左右两侧必定有一侧是严格有序的。

我们可以利用这一特性来缩小搜索范围：

1. 判断 mid 位置：首先检查 nums[mid] 是否等于 target，相等则直接返回。
2. 确定有序区间：比较 nums[left] 和 nums[mid]。
   • 若 nums[left] <= nums[mid]，说明左半部分 [left, mid] 是有序的。此时再判断 target 是否落在该区间内。若在，则收缩右边界 right = mid - 1；否则收缩左边界 left = mid + 1。
   • 若 nums[left] > nums[mid]，说明左半部分无序，那么右半部分 [mid, right] 必然是有序的。同样判断 target 是否在右半区间内，决定移动 left 还是 right。
3. 循环终止：当 left > right 时仍未找到，返回 -1。

这种逻辑确保了每次都能排除一半的无效区间，从而满足对数级时间复杂度的要求。

代码实现

下面是完整的 C++ 实现，包含了必要的注释以辅助理解逻辑分支。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        
        while (left <= right) {
            // 防止溢出的中间值计算
            int mid = left + (right - left) / 2;
            
            // 找到目标值直接返回
            if (nums[mid] == target) {
                return mid;
            }
            
            // 判断左半部分是否有序
            if (nums[left] <= nums[mid]) {
                // 左半部分有序，判断 target 是否在左半部分
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // 右半部分有序，判断 target 是否在右半部分
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        
        return -1;
    }
};

调试与验证

以输入 nums = [4,5,6,7,0,1,2], target = 0 为例：

初始状态 left = 0, right = 6。mid 指向 7，左侧有序但 target 不在 [4, 7] 之间，因此 left 移至 4。

第二次迭代 left = 4, right = 6。mid 指向 1，左侧 [0,1,2] 有序且包含 target，right 移至 4。

第三次迭代 left = 4, right = 4。mid 指向 0，匹配成功，返回索引 4。

整个过程清晰展示了如何利用局部有序性快速定位目标。

复杂度分析

• 时间复杂度：O(log n)。每次迭代都将搜索空间减半。
• 空间复杂度：O(1)。仅使用常数个变量。