本文详解如何在旋转排序数组中正确实现二分查找，指出原代码中“先找峰值再分段二分”的逻辑缺陷，并提供时间复杂度为 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 必将数组划分为“至少一侧严格有序”的两部分
。
以下是优化后的完整实现：
关键要点解析：
有序性判定
：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，结果正确。
总结：处理旋转排序数组搜索，应放弃“分治式”峰值定位思维，转而采用
基于区间有序性动态剪枝
的单次二分策略——它更简洁、健壮，且是面试与工程实践中的标准范式。
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
}
}