33. 搜索旋转排序数组

📝 题目描述

整数数组 nums 按升序排列，在传递给函数前，在某个下标 k 处进行了向左旋转（旋转后数组为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]）。数组元素互不相同，给定旋转后的数组和目标值 target，要求设计时间复杂度为 O(log n) 的算法，返回 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

---

🚀 最优解：二分查找（确定有序区间）

🔍 思路解析

核心策略：旋转数组可分为“左有序段”和“右有序段”，通过二分确定中点所在的有序段，再判断目标值是否在该有序段内，逐步缩小查找范围。

1. 初始化双指针 left=0、right=nums.length-1；
2. 当 left ≤ right 时，计算中点 mid = (left + right) / 2；
3. 若 nums[mid] == target，直接返回 mid；
4. 判断 mid 所在的有序段：
   • 若 nums[mid] ≥ nums[left]：mid 在左有序段，进一步判断 target 是否在 [nums[left], nums[mid]] 内：
     • 是 → 缩小范围到左半段（right = mid - 1）；
     • 否 → 缩小范围到右半段（left = mid + 1）；
   • 若 nums[mid] < nums[left]：mid 在右有序段，进一步判断 target 是否在 [nums[mid], nums[right]] 内：
     • 是 → 缩小范围到右半段（left = mid + 1）；
     • 否 → 缩小范围到左半段（right = mid - 1）；
5. 若循环结束未找到，返回 -1。

---

✅ 完整代码（Java）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        // 读取目标值
        int target = scanner.nextInt();

        // 创建解决方案对象并计算结果
        Solution solution = new Solution();
        int result = solution.search(nums, target);

        // 输出结果
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // 判断mid是否在左有序段
            if (nums[mid] >= nums[left]) {
                // 目标在左有序段内
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // mid在右有序段
            else {
                // 目标在右有序段内
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        // 未找到目标
        return -1;
    }
}

---

🧠 通俗易懂解释

可以把旋转数组理解为“两段独立的升序数组拼接而成”，比如 [4,5,6,7,0,1,2] 是 [4,5,6,7]（左有序段）和 [0,1,2]（右有序段）拼接的结果。 查找目标的过程类似“先确定在哪一段，再在该段内找”：

1. 每次取中点，先看中点属于左有序段还是右有序段；
2. 若中点在左有序段，就看目标是否在左有序段的范围内（比如目标是0，不在 [4,7] 里，就去右半部分找）；
3. 若中点在右有序段，同理判断目标是否在右有序段范围内；
4. 不断缩小范围，直到找到目标或确定不存在。

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

1. left=0, right=6，mid=3，nums[3]=7（左有序段），0不在 [4,7] 里 → 去右半部分，left=4；
2. left=4, right=6，mid=5，nums[5]=1（右有序段），0在 [0,2] 里 → 去左半部分，right=4；
3. left=4, right=4，mid=4，nums[4]=0 == target → 返回4。

---

⏱ 时间复杂度

O(log n)

每次二分将查找范围缩小一半，遍历次数为数组长度的对数级别。

---

💾 空间复杂度

O(1)

仅使用3个指针变量，无额外空间消耗。 nums[l] <= nums[mid]左段有序(反之右段有序)，再nums[mid] > target && target >= nums[l]可以得到目标在左有序段可以right = mid - 1