在旋转排序数组中高效查找目标值的完整解决方案

目前golang学习网上已经有很多关于文章的文章了，自己在初次阅读这些文章中，也见识到了很多学习思路；那么本文《在旋转排序数组中高效查找目标值的完整解决方案 》，也希望能帮助到大家，如果阅读完后真的对你学习文章有帮助，欢迎动动手指，评论留言并分享~

本文详解如何在旋转排序数组中正确实现二分查找，指出原代码中“先找峰值再分段二分”的逻辑缺陷，并提供时间复杂度为 O(log n) 的单次二分搜索标准解法，附带可运行示例与关键边界分析。

本文详解如何在旋转排序数组中正确实现二分查找，指出原代码中“先找峰值再分段二分”的逻辑缺陷，并提供时间复杂度为 O(log n) 的单次二分搜索标准解法，附带可运行示例与关键边界分析。

在旋转排序数组（如 [3,4,5,6,7,0,1,2]）中查找目标值，核心挑战在于：数组虽整体无序，但被分为两个连续升序子段，且存在唯一旋转点。原代码试图先定位峰值（即最大值索引），再对左右两段分别二分搜索——该思路看似合理，实则隐含严重缺陷：

• ✅ peak_ele() 方法虽能正确找到峰值索引（本例中为 4，对应元素 7），但未处理数组单调递增（即未旋转）的边界情况，且循环终止条件 start < end 在 arr.length == 1 时可能出错；
• ❌ 更关键的是，bs(arr, target, peak+1, arr.length-1) 调用时，右半段起始索引 peak+1 可能越界（如峰值在末尾），且即使不越界，右半段 [0,1,2] 是升序，但 bs() 函数本身是标准二分搜索，未适配“右半段最小值 > 左半段最大值”这一旋转特性——它仅假设传入区间本身有序，而原逻辑未确保 peak+1 到 end 确为升序段（实际是，但调用方式暴露设计冗余）；
• ⚠️ 最致命问题：当目标值位于左段时，若 bs() 在左段未找到（返回 -1），代码会无条件进入右段搜索；但若目标值根本不在数组中，两次 bs() 均失败，最终仍返回 -1 —— 这看似正常，然而 peak_ele() 的边界处理不鲁棒（如 mid+1 越界访问）、且分段逻辑未覆盖所有旋转形态（如 [1,3] 或 [2,1]），导致稳定性差。

因此，业界标准解法是不显式寻找峰值，而是在单次二分过程中动态判断哪一侧有序，并据此收缩搜索区间。其依据是：任意中点 mid 必将数组划分为“至少一侧严格有序”的两部分。

以下是优化后的完整实现：

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

        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] == target) {
                return mid; // 找到目标，直接返回
            }

            // 判断左半段 [start, mid] 是否有序
            if (nums[start] <= nums[mid]) {
                // 左段有序：检查target是否在左段范围内
                if (target >= nums[start] && target < nums[mid]) {
                    end = mid - 1; // target在左段，收缩右边界
                } else {
                    start = mid + 1; // target不在左段，搜右段
                }
            } else {
                // 右半段 [mid, end] 必然有序（因数组仅旋转一次）
                // 检查target是否在右段范围内
                if (target > nums[mid] && target <= nums[end]) {
                    start = mid + 1; // target在右段，收缩左边界
                } else {
                    end = mid - 1; // target不在右段，搜左段
                }
            }
        }
        return -1; // 未找到
    }

    public static void main(String[] args) {
        int[] arr = {3, 4, 5, 6, 7, 0, 1, 2};
        int target = 1;
        int index = search(arr, target);
        System.out.println("Index of " + target + " is " + index); // 输出: Index of 1 is 6
    }
}

关键要点解析：

• 有序性判定：nums[start] <= nums[mid] 成立，说明 [start, mid] 升序（含单元素情形）；否则 [mid, end] 升序。这是旋转数组的核心性质。
• 范围检查严谨性：左段有序时，target < nums[mid]（非 <=）是因为 nums[mid] 已在上一步排除；同理右段用 target > nums[mid]。
• 边界安全：全程使用 start <= end 和 mid = start + (end-start)/2，避免整数溢出与死循环。
• 时间复杂度：O(log n)，空间复杂度：O(1)，优于先找峰再搜索的两遍 O(log n)（常数因子更大且易出错）。

测试验证：对输入 {3,4,5,6,7,0,1,2} 查找 1，算法在第 3 次迭代中 mid=6，nums[6]=1，直接返回索引 6，结果正确。

总结：处理旋转排序数组搜索，应放弃“分治式”峰值定位思维，转而采用基于区间有序性动态剪枝的单次二分策略——它更简洁、健壮，且是面试与工程实践中的标准范式。

今天关于《在旋转排序数组中高效查找目标值的完整解决方案 》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于的内容请关注golang学习网公众号！