本文详解旋转排序数组的二分查找原理与实现，指出先找峰值再分段搜索的常见误区，提供标准o(log n)解法，并通过代码示例与逻辑分析帮助开发者彻底掌握该经典算法。
本文详解旋转排序数组的二分查找原理与实现，指出先找峰值再分段搜索的常见误区，提供标准o(log n)解法，并通过代码示例与逻辑分析帮助开发者彻底掌握该经典算法。
在旋转排序数组（如 [3,4,5,6,7,0,1,2]）中查找目标值时，直接套用普通二分查找会失败——因为数组整体无序，但被旋转点分割后的左右两段各自有序。原代码试图先定位峰值（即最大值索引），再对左右两段分别二分搜索，看似合理，实则存在两个关键缺陷：
- 峰值识别逻辑不鲁棒：peak_ele() 方法在边界处理上未覆盖所有情况（如数组长度为1、峰值位于首尾），且循环终止条件 start
- 分段搜索前提错误：即使峰值定位准确，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 = nums[start] && target nums[mid] && target <p>? <strong>关键注意事项</strong>： </p>
- nums[start]
- 边界比较使用
- 该算法天然兼容无旋转数组（即单调递增），也适用于含重复元素的变种（需额外处理，此处假设元素唯一）。
? 总结：旋转数组搜索的本质，是利用“至少一侧子数组必然有序”的数学性质，在每次二分中淘汰一半无效区间。放弃“先找峰再分治”的直觉思路，转向“边查边判序”的统一二分框架，既提升鲁棒性，又降低实现复杂度。掌握此模式，可轻松迁移解决类似问题（如查找最小值、统计出现次数等）。
