跳到主要内容

二分查找模板

二分查找的前提是什么？​

  • 数据必须有序 (升序或降序), 或具有可判定的单调性;
  • 每轮比较中间元素即可排除一半区间;

中间下标如何计算？​

  • 推荐写法: mid = Math.floor(left + (right - left) / 2);
  • (left + right) / 2 在极端大下标下可能溢出整数范围, 先减后除可避免;
  • 向下取整保证 mid 不会等于 right;

左闭右开的区间约定是什么？​

  • 统一使用 left < right, 循环结束时 left 与 right 重合;
  • 区间为 [left, right), right 初值取 nums.length;
  • 基于 mid 缩小时: right 取 mid (保持开区间), left 取 mid + 1 (保持闭区间);
  • 若第一次比较就需要使用末元素, right 初值改取 nums.length - 1;

循环结束后如何取结果？​

  • 结束时 left === right, 答案只可能在 left (或 left - 1) 处;
  • 答案可能不存在时, 必须在循环外检查 nums[left] === target;
  • left 可能递增到数组末尾之外, 检查前需先判断下标是否越界;

二分查找如何实现？​

function search(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length;
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (target === nums[mid]) return mid;
    else if (target < nums[mid]) right = mid;
    else left = mid + 1;
  }
  if (nums[left] === target) return left;
  return -1;
}
  • 时间复杂度: O(log n);
  • 空间复杂度: O(1);