手帐 Blog

主题

14 · 二分查找标准模板 ​

目标：默写不越界的 l / r / mid 模板；会做搜索插入位置。

为什么面试会考 ​

有序数组里找数，暴力 O(n)，二分 O(log n)。面试官爱考边界：

  • while 用 l <= r 还是 l < r？
  • mid 取整向上还是向下？
  • 找不到时返回什么？

模板背熟，变体题才不会每次重推。

零基础概念 ​

每次把搜索区间砍一半：

text
有序数组: [1, 3, 5, 7, 9]，找 7
第一次 mid=5，7>5 → 丢左边
第二次 mid=7，找到

mid 建议：l + ((r - l) >> 1)，避免某些语言里 l+r 溢出；JS 里 Math.floor((l+r)/2) 一般也够用。

JS 模板（闭区间 [l, r]） ​

js
function binarySearch(nums, target) {
  let l = 0
  let r = nums.length - 1
  while (l <= r) {
    const mid = l + ((r - l) >> 1)
    if (nums[mid] === target) return mid
    if (nums[mid] < target) l = mid + 1
    else r = mid - 1
  }
  return -1
}

记住：排除 mid 后，l = mid + 1 或 r = mid - 1，区间才会缩小。

精讲题 ​

LeetCode 704. 二分查找 ​

js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let l = 0
  let r = nums.length - 1
  while (l <= r) {
    const mid = l + ((r - l) >> 1)
    if (nums[mid] === target) return mid
    if (nums[mid] < target) l = mid + 1
    else r = mid - 1
  }
  return -1
}

LeetCode 35. 搜索插入位置 ​

有序数组中找 target；没有则返回应插入的下标（第一个 >= target 的位置）。

循环结束时，l 正好是插入点。

js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  let l = 0
  let r = nums.length - 1
  while (l <= r) {
    const mid = l + ((r - l) >> 1)
    if (nums[mid] === target) return mid
    if (nums[mid] < target) l = mid + 1
    else r = mid - 1
  }
  return l
}

小例子：找第一个大于等于 target 的位置（下界） ​

与 35 同构，可当默写练习：

js
function lowerBound(nums, target) {
  let l = 0
  let r = nums.length // 半开 [l, r)
  while (l < r) {
    const mid = l + ((r - l) >> 1)
    if (nums[mid] < target) l = mid + 1
    else r = mid
  }
  return l
}

练习清单 ​

题提示
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置两次二分：下界 + 上界
LeetCode 69. x 的平方根在答案空间二分
LeetCode 278. 第一个错误的版本API isBadVersion，找第一个 true
LeetCode 367. 有效的完全平方数二分 mid*mid 与 num 比较

今日验收 ​

  • [ ] 能默写 704 闭区间模板
  • [ ] 能解释 35 为何返回 l
  • [ ] 知道 l<=r 与 l<r 两套写法不要混用边界更新

若你以前见过 ​

「二分」不是只会查数组下标；后面「答案二分」是在答案的取值范围上二分。