搜索旋转排序数组：五种实现方案详解

2.3 破题关键

1. 判断有序部分：在二分查找的每一步，通过比较 nums[mid] 与 nums[left] 来判断左半部分是否有序
2. 目标值定位：
   • 如果左半部分有序且 target 在左半部分的范围内，则搜索左半部分
   • 如果右半部分有序且 target 在右半部分的范围内，则搜索右半部分
   • 否则搜索另一部分
3. 边界条件：注意处理单元素数组、空数组（根据提示，长度至少为 1）、目标值等于边界值等情况
4. 循环终止：标准二分查找的循环终止条件

3.算法设计与实现

3.1 标准二分查找（一次遍历）

核心思想：

在二分查找的过程中，通过判断 mid 所在的有序部分，来确定搜索方向。每次将搜索空间减半，保持 O(log n) 时间复杂度。

算法思路：

1. 初始化 left = 0, right = nums.length - 1
2. 当 left <= right 时循环：
   • 计算 mid = left + (right - left) / 2
   • 如果 nums[mid] == target，直接返回 mid
   • 判断哪部分是有序的：
     • 如果 nums[left] <= nums[mid]，说明左半部分 [left, mid] 是有序的
       • 如果 target 在 [nums[left], nums[mid]] 范围内，则 right = mid - 1
       • 否则 left = mid + 1
     • 否则，右半部分 [mid, right] 是有序的
       • 如果 target 在 [nums[mid], nums[right]] 范围内，则 left = mid + 1
       • 否则 right = mid - 1
3. 循环结束未找到，返回 -1

Java 代码实现：

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 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]) {
                    // target 在有序的左半部分
                    right = mid - 1;
                } else {
                    // target 在右半部分
                    left = mid + 1;
                }
            } else {
                // 右半部分有序
                if (nums[mid] < target && target <= nums[right]) {
                    // target 在有序的右半部分
                    left = mid + 1;
                } else {
                    // target 在左半部分
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

性能分析：

• 时间复杂度：O(log n)，每次将搜索区间减半
• 空间复杂度：O(1)，只使用常数个变量
• 优点：一次遍历，效率高，代码相对简洁
• 缺点：条件判断稍微复杂，需要仔细处理边界条件

3.2 先找旋转点，再二分查找

核心思想：

先通过二分查找找到旋转点（即数组中最小的元素，也是旋转的分界点），然后根据 target 与 nums[0] 的比较结果，决定在旋转点的哪一侧进行二分查找。

算法思路：

1. 找到旋转点 pivot（最小值的位置）：
   • 如果 nums[left] <= nums[right]，说明数组没有旋转或旋转了整数倍，pivot = 0
   • 否则，使用二分查找找到旋转点
2. 根据 target 与 nums[0] 的比较，确定搜索区间：
   • 如果 target >= nums[0]，在 [0, pivot-1] 区间搜索（如果 pivot == 0 则在完整数组搜索）
   • 否则，在 [pivot, nums.length-1] 区间搜索
3. 在确定的区间内执行标准二分查找

Java 代码实现：

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        // 1. 找到旋转点（最小值的位置）
        int pivot = findPivot(nums);
        // 2. 根据 target 决定在哪一部分搜索
        if (pivot == 0) {
            // 数组没有旋转或旋转了整数倍
            return binarySearch(nums, target, 0, nums.length - 1);
        }
        if (target >= nums[0]) {
            // target 在旋转点的左侧（包括 nums[0]）
            return binarySearch(nums, target, 0, pivot - 1);
        } else {
            // target 在旋转点的右侧
            return binarySearch(nums, target, pivot, nums.length - 1);
        }
    }

    // 查找旋转点（最小值的位置）
    private int findPivot(int[] nums) {
        int left = 0, right = nums.length - 1;
        // 如果数组没有旋转，直接返回 0
        if (nums[left] <= nums[right]) {
            return 0;
        }
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 检查 mid 是否是旋转点
            if (mid > 0 && nums[mid] < nums[mid - 1]) {
                return mid;
            }
            // 判断旋转点在左半部分还是右半部分
            if (nums[mid] > nums[right]) {
                // 旋转点在右半部分
                left = mid + 1;
            } else {
                // 旋转点在左半部分
                right = mid - 1;
            }
        }
        return left;
    }

    // 标准二分查找
    private int binarySearch(int[] nums, int target, int left, int right) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

性能分析：

• 时间复杂度：O(log n)，两次二分查找
• 空间复杂度：O(1)
• 优点：逻辑清晰，分步进行，易于理解和调试
• 缺点：需要两次二分查找，代码量较大

3.3 递归实现二分查找

核心思想：

使用递归方式实现解法一的思路，递归函数接受搜索区间参数，在每次递归中判断有序部分并决定递归方向。

算法思路：

1. 定义递归函数 searchRecursive(nums, target, left, right)
2. 基本情况：如果 left > right，返回 -1
3. 计算 mid，如果找到目标返回 mid
4. 判断哪部分有序，递归搜索相应部分
5. 主函数调用递归函数

Java 代码实现：

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        return searchRecursive(nums, target, 0, nums.length - 1);
    }

    private int searchRecursive(int[] nums, int target, int left, int right) {
        if (left > right) {
            return -1;
        }
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        // 判断左半部分是否有序
        if (nums[left] <= nums[mid]) {
            // 左半部分有序
            if (nums[left] <= target && target < nums[mid]) {
                // target 在有序的左半部分
                return searchRecursive(nums, target, left, mid - 1);
            } else {
                // target 在右半部分
                return searchRecursive(nums, target, mid + 1, right);
            }
        } else {
            // 右半部分有序
            if (nums[mid] < target && target <= nums[right]) {
                // target 在有序的右半部分
                return searchRecursive(nums, target, mid + 1, right);
            } else {
                // target 在左半部分
                return searchRecursive(nums, target, left, mid - 1);
            }
        }
    }
}

性能分析：

• 时间复杂度：O(log n)
• 空间复杂度：O(log n)，递归调用栈深度
• 优点：递归思路清晰，符合分治思想
• 缺点：递归有栈溢出风险（虽然本题 n≤5000，栈深度 log₂(5000)≈13，安全）

3.4 暴力搜索（不符合要求，但作为对比）

核心思想：

线性扫描整个数组，查找目标值。虽然简单，但不满足时间复杂度要求。

算法思路：

1. 遍历数组的每个元素
2. 如果找到目标值，返回其索引
3. 遍历结束未找到，返回 -1

Java 代码实现：

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

性能分析：

• 时间复杂度：O(n)，最坏情况下需要遍历整个数组
• 空间复杂度：O(1)
• 优点：代码极其简单，易于实现
• 缺点：不满足题目要求的 O(log n) 时间复杂度

3.5 改进的二分查找（统一条件判断）

核心思想：

将解法一中的条件判断进行简化和统一，使用更简洁的条件表达式。

算法思路：

1. 标准的二分查找循环结构
2. 统一条件判断：始终检查 target 是否在有序部分内
3. 通过异或运算简化条件判断（可选，但可能降低可读性）

Java 代码实现：

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // 判断 mid 和 target 是否在同一侧（相对于旋转点）
            boolean isMidInLeft = nums[mid] >= nums[left];
            boolean isTargetInLeft = target >= nums[left];
            if (isMidInLeft && !isTargetInLeft) {
                // mid 在左半部分，target 在右半部分
                left = mid + 1;
            } else if (!isMidInLeft && isTargetInLeft) {
                // mid 在右半部分，target 在左半部分
                right = mid - 1;
            } else {
                // mid 和 target 在同一侧，执行标准二分查找
                if (nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

性能分析：

• 时间复杂度：O(log n)
• 空间复杂度：O(1)
• 优点：条件判断逻辑统一，代码结构清晰
• 缺点：需要理解'在同一侧'的概念

4.性能对比

4.1 复杂度对比表

4.2 实际性能测试

测试环境：JDK 17，数组长度 5000，随机生成数据并旋转，运行 10000 次取平均值

4.3 各场景适用性分析

1. 面试场景：推荐标准二分查找，展示对旋转数组特性的理解和二分查找的掌握
2. 竞赛场景：推荐标准二分查找或改进二分查找，代码简洁高效
3. 生产环境：推荐标准二分查找，经过充分测试，可靠性高
4. 练习场景：推荐递归实现，有助于理解分治思想；或先找旋转点再二分，逻辑清晰
5. 多次查询场景：推荐先找旋转点再二分，找到旋转点后可以快速进行多次查询

5.扩展与变体

5.1 搜索旋转排序数组 II（有重复元素）

题目描述：已知存在一个按非降序排列的整数数组，数组中的值不必互不相同。在传递给函数之前，数组在某个下标上进行了旋转。编写一个函数来判断给定的目标值是否存在于数组中。如果存在则返回 true，否则返回 false。

Java 代码实现：

class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return true;
            }
            // 处理重复元素：当左右边界与中间值相等时，无法判断哪部分有序
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                left++;
                right--;
            } else if (nums[left] <= nums[mid]) {
                // 左半部分有序
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // 右半部分有序
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
}

5.2 寻找旋转排序数组中的最小值

题目描述：已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。请找出其中最小的元素。

Java 代码实现：

class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        // 如果数组没有旋转，第一个元素就是最小值
        if (nums[left] <= nums[right]) {
            return nums[left];
        }
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 检查 mid 是否是最小值
            if (mid > 0 && nums[mid] < nums[mid - 1]) {
                return nums[mid];
            }
            if (mid < nums.length - 1 && nums[mid] > nums[mid + 1]) {
                return nums[mid + 1];
            }
            // 判断最小值在哪一侧
            if (nums[mid] > nums[right]) {
                // 最小值在右半部分
                left = mid + 1;
            } else {
                // 最小值在左半部分
                right = mid - 1;
            }
        }
        return nums[left];
    }
}

5.3 寻找旋转排序数组中的最小值 II（有重复元素）

题目描述：已知一个按非降序排列的整数数组，数组中的值不必互不相同。在传递给函数之前，数组在某个下标上进行了旋转。请找出其中最小的元素。

Java 代码实现：

class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                // 最小值在右半部分
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                // 最小值在左半部分（包括 mid）
                right = mid;
            } else {
                // nums[mid] == nums[right]，无法判断，缩小右边界
                right--;
            }
        }
        return nums[left];
    }
}

5.4 搜索旋转排序数组中的目标值范围

题目描述：在旋转排序数组中，找到目标值的起始和结束位置。如果数组中不存在目标值，返回 [-1, -1]。

Java 代码实现：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        if (nums == null || nums.length == 0) {
            return result;
        }
        // 先找到一个目标值的位置
        int index = search(nums, target);
        if (index == -1) {
            return result;
        }
        // 向左扩展找到起始位置
        int left = index;
        while (left > 0 && nums[left - 1] == target) {
            left--;
        }
        // 向右扩展找到结束位置
        int right = index;
        while (right < nums.length - 1 && nums[right + 1] == target) {
            right++;
        }
        result[0] = left;
        result[1] = right;
        return result;
    }

    // 使用标准二分查找在旋转数组中搜索目标值
    private int search(int[] nums, int target) {
        int left = 0, right = nums.length - 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;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

6.总结

6.1 核心思想总结

1. 旋转数组特性：旋转后的数组由两个有序部分组成，且前半部分的所有元素都大于后半部分的所有元素（当数组元素互不相等时）
2. 二分查找的适应性：即使数组不是完全有序，只要能够判断哪一部分是有序的，就可以使用二分查找
3. 判断有序部分：通过比较 nums[mid] 与 nums[left] 或 nums[right] 可以判断 mid 所在的部分是否有序
4. 目标值定位：在确定有序部分后，检查 target 是否在该有序部分的范围内，从而决定搜索方向
5. 处理重复元素：当数组包含重复元素时，需要特殊处理 nums[left] == nums[mid] == nums[right] 的情况

6.2 实际应用场景

1. 日志分析：在循环日志缓冲区中查找特定时间戳的记录
2. 数据库查询：在部分有序的索引中高效查找数据
3. 游戏开发：在旋转后的排行榜或分数列表中查找玩家排名
4. 时间序列分析：处理周期性数据或旋转后的时间序列
5. 文件系统：在循环缓冲区或环形数据结构中查找数据

6.3 面试建议

1. 理解原理：不仅要会写代码，还要能解释为什么在旋转数组中仍然可以使用二分查找
2. 手写代码：能够手写标准二分查找解法，注意边界条件的处理
3. 测试用例：准备各种测试用例：单元素数组、未旋转数组、完全旋转数组、目标值在边界、目标值不存在等
4. 复杂度分析：能够清晰分析时间复杂度和空间复杂度
5. 扩展思考：了解相关变体问题，展示知识广度

6.4 常见面试问题 Q&A

Q1：为什么在旋转数组中仍然可以使用二分查找？
A1：因为旋转数组虽然整体不是有序的，但它由两个有序部分组成。在二分查找的每一步，我们可以通过比较 nums[mid] 与边界值来判断哪一部分是有序的，然后检查 target 是否在这个有序部分内，从而将搜索空间减半。

Q2：如何处理数组中有重复元素的情况？
A2：当有重复元素时，可能会出现 nums[left] == nums[mid] == nums[right] 的情况，此时无法判断哪部分有序。处理方法是同时缩小左右边界（left++, right--），继续搜索。

Q3：这个算法在最坏情况下的时间复杂度是多少？
A3：当数组元素互不相同时，时间复杂度为 O(log n)。当数组包含重复元素时，最坏情况下时间复杂度为 O(n)，例如当所有元素都相等且不等于目标值时。

Q4：如何找到旋转点（最小值的位置）？
A4：可以使用二分查找找到旋转点：如果 nums[mid] > nums[right]，说明旋转点在右半部分，否则在左半部分。当找到 nums[mid] < nums[mid-1] 时，mid 就是旋转点。

Q5：如果数组没有旋转，这个算法还能工作吗？
A5：可以。当数组没有旋转时，nums[left] <= nums[mid] 始终成立，算法退化为标准二分查找，仍然能够正确工作。