本文详解旋转排序数组的二分查找原理与实现，指出先找峰值再分段搜索的常见误区，提供标准o(log n)解法，并通过代码示例与逻辑分析帮助开发者彻底掌握该经典算法。
本文详解旋转排序数组的二分查找原理与实现，指出先找峰值再分段搜索的常见误区，提供标准o(log n)解法，并通过代码示例与逻辑分析帮助开发者彻底掌握该经典算法。
在旋转排序数组（如 [3,4,5,6,7,0,1,2]）中查找目标值时，直接套用普通二分查找会失败——因为数组整体无序，但被旋转点分割后的左右两段各自有序。原代码试图先定位峰值（即最大值索引），再对左右两段分别二分搜索，看似合理，实则存在两个关键缺陷：
- 峰值识别逻辑不鲁棒：peak_ele() 方法在边界处理上未覆盖所有情况（如数组长度为1、峰值位于首尾），且循环终止条件 start < end 导致 end 可能越界或未收敛；
- 分段搜索前提错误：即使峰值定位准确，bs(arr, target, 0, peak) 仅搜索左段（升序），而 bs(arr, target, peak+1, arr.length-1) 搜索右段（也升序），但右段的起始值小于左段末值，目标值可能“跨段”存在——例如目标 1 在右段 [0,1,2] 中，但原代码调用 bs(..., peak+1, ...) 时传入的 start 和 end 范围正确，问题实际出在：peak_ele 返回值错误导致分段失效。
以输入 arr = {3,4,5,6,7,0,1,2} 为例：
- 正确峰值索引应为 4（对应元素 7），但原 peak_ele 因 mid+1 越界风险及循环终止逻辑缺陷，可能返回错误位置（如 5 或 6），致使后续二分搜索范围错误。
✅ 推荐解法：单次二分，动态判断有序侧
核心思想：每次迭代确定 mid 所在的哪一侧子数组是严格有序的，再判断目标是否落在该有序区间内，从而决定搜索方向。无需预先找峰值，时间复杂度稳定 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; // 找到目标，直接返回
}
// 判断左半段 [start, mid] 是否有序
if (nums[start] <= nums[mid]) {
// 左段有序：检查target是否在左段范围内
if (target >= nums[start] && target < nums[mid]) {
end = mid - 1; // 在左段搜索
} else {
start = mid + 1; // 否则在右段搜索
}
}
// 否则右半段 [mid, end] 必然有序（因数组仅旋转一次）
else {
// 右段有序：检查target是否在右段范围内
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); // 输出: Index of 1 is 6
}
}? 关键注意事项：
- nums[start] <= nums[mid] 判断左段有序时，等号必不可少——当 start == mid（如数组长度为1或2时），需确保逻辑覆盖；
- 边界比较使用 <= 和 < 需严格匹配区间定义（如左段 [start, mid] 有序，则 target < nums[mid] 排除 mid 自身，因已在前一步验证）；
- 该算法天然兼容无旋转数组（即单调递增），也适用于含重复元素的变种（需额外处理，此处假设元素唯一）。
? 总结：旋转数组搜索的本质，是利用“至少一侧子数组必然有序”的数学性质，在每次二分中淘汰一半无效区间。放弃“先找峰再分治”的直觉思路，转向“边查边判序”的统一二分框架，既提升鲁棒性，又降低实现复杂度。掌握此模式，可轻松迁移解决类似问题（如查找最小值、统计出现次数等）。
