JS二分查找实践：如何建立峰值谷值查找的统一思维模型

这类二分极值问题的统一思维模型 #

核心是抓住「区间不变性」和「循环终止状态」两个关键点，完全不需要靠试错确定返回值：

核心逻辑 #

首先明确：你每次收缩区间的操作，必须保证剩余区间一定包含至少一个符合要求的目标，只要遵循这个规则，就可以用更简单的循环条件规避返回值二选一的问题。

优先使用「左闭右闭+left<right」的写法 #

不要用left <= right作为循环条件，改用left < right，循环终止时left和right完全相等，直接返回任意一个都可以，完全不用纠结：

找峰值的优化写法

var findPeakElement = function(nums) {
    if(nums.length <= 1) return 0
    let left = 0, right = nums.length - 1
    while(left < right) {
        const mid = left + right >>> 1
        // mid比右边大，峰值一定在左半段（含mid）
        if(nums[mid] > nums[mid + 1]) {
            right = mid // 不-1，mid本身可能是峰值
        } 
        // mid比右边小，峰值一定在右半段（不含mid）
        else {
            left = mid + 1
        }
    }
    // 循环终止时left===right，直接返回即可
    return left
}

找谷值的优化写法

var findValleyElement = function (nums) {
  if (nums.length <= 1) return 0
  let left = 0, right = nums.length - 1
  while (left < right) {
    const mid = (left + right) >>> 1
    // mid比右边大，谷值一定在右半段（不含mid）
    if (nums[mid] > nums[mid + 1]) {
      left = mid + 1
    } 
    // mid比右边小，谷值一定在左半段（含mid）
    else {
      right = mid
    }
  }
  // 循环终止时left===right，直接返回即可
  return left
}

原有left<=right写法的返回值判断逻辑 #

如果你坚持要用left<=right的循环条件，记住循环终止时的固定状态是right = left - 1，两个指针刚好错开，你只需要判断：你要找的目标是「第一个满足某条件的位置」还是「最后一个满足某条件的位置」：

• 找峰值相当于找「第一个比右侧元素大的位置」，对应left指针的位置
• 找谷值相当于找「第一个比右侧元素小的位置」，同样对应left指针的位置

所以不管找峰值还是谷值，只要你遵循前面的收缩逻辑，用left<=right时返回left都可以，你的谷值代码返回right不对就是因为终止时right比left小1，不在目标位置上。

内容的提问来源于stack exchange，提问作者Joji