峰值与最值问题

寻找峰值为什么可以用二分？

• 条件: 相邻元素不相等, 可把两端视为负无穷;
• 性质: nums[mid] < nums[mid + 1] 说明右半侧必然存在峰值, 否则左半侧 (含 mid) 必然存在峰值;
• 于是可沿上升方向不断收缩区间;

function findPeakElement(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] > nums[mid + 1]) right = mid;
    else left = mid + 1;
  }
  return left;
}

如何用二分求平方根？

• 问题: 求满足 k^2 <= x 的最大整数 k;
• 答案空间为 [0, x], 每轮比较 mid^2 与 x;
• mid^2 大于 x 时 right = mid, 否则 left = mid + 1;
• 循环可能以 left 略大于答案结束, 需要在循环外向下取整判断;

function mySqrt(x: number): number {
  let left = 0;
  let right = x;
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    const value = mid * mid;
    if (value === x) return mid;
    else if (value > x) right = mid;
    else left = mid + 1;
  }
  return left * left > x ? left - 1 : left;
}

为什么二分查找可以不依赖真实数组？

• 二分只依赖单调性与可判定的中点比较, 不要求真的存在数组;
• 只要能把问题写成"答案空间中单调判定", 就能二分;
• 峰值、平方根、插入点都是这种建模;
• 时间复杂度均为 O(log n), 空间复杂度 O(1);