本文详解如何在旋转排序数组中正确实现二分查找，指出原代码中“先找峰值再分段二分”的逻辑缺陷，并提供时间复杂度为 o(log n) 的单次二分搜索标准解法，附带可运行示例与关键边界分析。
本文详解如何在旋转排序数组中正确实现二分查找，指出原代码中“先找峰值再分段二分”的逻辑缺陷，并提供时间复杂度为 o(log n) 的单次二分搜索标准解法，附带可运行示例与关键边界分析。
在旋转排序数组（如 [3,4,5,6,7,0,1,2]）中查找目标值，核心挑战在于：数组虽整体无序，但被分为两个连续升序子段，且存在唯一旋转点。原代码试图先定位峰值（即最大值索引），再对左右两段分别二分搜索——该思路看似合理，实则隐含严重缺陷：
- ✅ peak_ele() 方法虽能正确找到峰值索引（本例中为 4，对应元素 7），但未处理数组单调递增（即未旋转）的边界情况，且循环终止条件 start
- ❌ 更关键的是，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 = nums[start] && target nums[mid] && target <p><strong>关键要点解析：</strong> </p>
- 有序性判定：nums[start]
- 范围检查严谨性：左段有序时，target nums[mid]。
- 边界安全：全程使用 start
- 时间复杂度：O(log n)，空间复杂度：O(1)，优于先找峰再搜索的两遍 O(log n)（常数因子更大且易出错）。
测试验证：对输入 {3,4,5,6,7,0,1,2} 查找 1，算法在第 3 次迭代中 mid=6，nums[6]=1，直接返回索引 6，结果正确。
总结：处理旋转排序数组搜索，应放弃“分治式”峰值定位思维，转而采用基于区间有序性动态剪枝的单次二分策略——它更简洁、健壮，且是面试与工程实践中的标准范式。
