本文详解如何在旋转排序数组中正确实现二分查找，指出原代码中“先找峰值再分段搜索”的逻辑缺陷，并提供标准的单次二分解决方案，附带可运行示例与关键边界分析。
本文详解如何在旋转排序数组中正确实现二分查找，指出原代码中“先找峰值再分段搜索”的逻辑缺陷，并提供标准的单次二分解决方案，附带可运行示例与关键边界分析。
在旋转排序数组（如 [3,4,5,6,7,0,1,2]）中查找目标值，不能简单套用普通二分查找，也不能依赖“先定位峰值、再分两段搜索”的策略——因为该策略存在两个致命隐患：峰值定位不鲁棒（如数组无严格峰值或全等元素），且分段后二分区间判断缺失对目标值分布的动态验证，导致右半段（如 peak+1 到 length-1）的搜索可能跳过实际解。
原代码中 peak_ele() 方法虽能找出最大值索引（即旋转点前一位），但其循环终止条件 while(start < end) 在 start == end 时退出，返回 end 是正确的；问题核心在于后续调用 bs(arr, target, peak+1, arr.length-1) 时，未校验该区间是否真正有序且可能包含目标值。例如，当 target = 1 时，峰值为 4（对应元素 7），右半段为 [0,1,2]，看似合理——但 bs() 函数本身是标准升序二分，而它被错误地应用于一个未做有效性预判的子区间：若目标值实际位于左段（如 target=5），右段搜索必然失败并返回 -1，此时程序不会回退重试，直接输出错误结果。
更本质、更高效的解法是：不显式寻找峰值，而在每次二分中动态判断哪一侧有序，并据此收缩搜索范围。核心思想是——旋转数组任一中点 mid 必将数组划分为「一侧严格有序、另一侧可能旋转」的两部分。通过比较 nums[start] 与 nums[mid] 即可判定左半是否有序：
- 若 nums[start] <= nums[mid]：左半 [start, mid] 有序 → 检查 target 是否落在该有序区间内（即 nums[start] <= target < nums[mid]），是则搜索左半，否则搜右半；
- 否则（nums[start] > nums[mid]）：右半 [mid, end] 有序 → 检查 target 是否落在 nums[mid] < target <= nums[end] 内，是则搜右半，否则搜左半。
该逻辑覆盖所有边界，时间复杂度稳定为 O(log n)，且无需额外峰值扫描。
以下是修正后的完整可运行代码：
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;
}
// 左半部分有序
if (nums[start] <= nums[mid]) {
if (target >= nums[start] && target < nums[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
// 右半部分有序
else {
if (target > nums[mid] && target <= nums[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
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); // 输出：6
}
}✅ 关键注意事项：
- nums[start] <= nums[mid] 中的等号不可省略，用于处理只有两个元素（如 [2,1]）或单元素数组的边界；
- 区间判断必须严格匹配有序侧的上下界（如左有序时用 target < nums[mid] 而非 <=，因 == 已在上一步被排除）；
- 不需要单独处理 nums[mid] == nums[start] 的重复情况（本题默认无重复），如有重复需额外去重逻辑；
- 初始化检查 nums == null || nums.length == 0 提升健壮性。
总结：旋转数组搜索的本质不是“还原秩序”，而是“利用局部有序性做决策”。摒弃分治式峰值预处理，转而采用一次遍历中的动态有序判断，才是简洁、正确、高性能的标准解法。
