跳到主要内容

力扣704-二分查找

· 阅读需 9 分钟
Yana Ching
Yana Ching
Front End Engineer

二分法​

  1. 适用于有序数据集合或者单调问题，用于快速查找 target、min、max
  2. 不适合动态数据结构（链表、树）、小规模数据

力扣 704-二分法 🔗

使用范围​

  1. 在已排序的数组或链表中查找 目标值的位置 或 验证该值是否存在
  2. 区间内寻找最大/小值（max/min）

限制​

  1. 必须有序，若数据无序，需要先排序会增加时间复杂度
  2. 不是动态数据结构（链表、树等），二分法要求直接访问中间元素
  3. 不适合规模小的集合，少量数据线性查找更加简单直接

手写代码注意​

1. 确保中间元素下标为整型（integer）​

2. 明确区间的定义，保证代码整体保持这个区间原则​

3. 外部 while 循环条件注意不能违反区间定义​

如果假设区间为[left, right]， 左右均闭合的区间存在相等的情况，因此 while 条件可以有相等的情况

如果假设区间为 [left, right)、（left, right]， 则左右相等的情况是相悖于这个假设的区间定义的，不存在相等的情况

4. 内部循环判断 nums[mid] 与 target 的大小关系时，明确 nums[mid] 可否加入下一次循环​

如果将已经排除的 nums[mid] 重新置入循环中，有导致整个算法死循环的风险，因此更新 left、right 范围的时候，需要明确 nums[mid] 本身是否可以继续加入下一个循环

优化点：确保中间元素的下标 mid 为整型（int）​

  • 使用 Math.floor() 向下取整 ---- 最常见、可读性高

  • 使用位操作的右移运算符 >>1 ---- 性能最优

    • (left + right) >> 1 相当于 (left + right) / 2 并取整，同时性能更优

  • left + Math.floor((right - left) / 2) ---- 避免 left、right 非常大的时候整数溢出

  • parseInt((left + right) / 2) ---- 相比 Math.floor、位操作符性能稍差

  • Math.trunc((left + right) / 2) ---- 无论正数负数，直接去除小数部分，相比位操作性能稍差

如果需要最简单、直观的整数截断（特别是负数时），Math.trunc() 是理想选择。

如果主要处理正数且性能要求不高，Math.floor() 也是常用的选择。

如果需要极高的性能或对位运算有特殊需求，位移操作符 >> 更高效。

为什么采取 Math.floor() 向下取整，而非向上取整 Math.ceil()​

  1. 避免死循环

一些情况下向上取整导致 永远无法缩小 左右区间

（尤其是数组长度为 奇数 时，向上取整会导致额外的复杂性）

  1. 平衡性（稳定性与可预测性）

Math.floor() 保证左右区间划分均衡

Math.floor()：每次迭代中左区间可能比右区间稍大，但变化是一致的，划分的过程是可预测和稳定的。

Math.ceil()：左右区间的划分有时左大，有时右大，变化是不稳定的，尤其在奇数长度的区间里，右侧会比左侧更小。

  1. 实践验证

长期时间验证，Math.floor() 相对于 Math.ceil() 在处理边界值和更新左右指针时的复杂度明显下降

>> 与 >>> 有什么区别？​

  1. >> 有符号右移，会根据符号位填充高位，保留负数的符号【高位正数补 0、负数补 1】
  2. >>> 无符号右移，不管符号，总是用 0 填充高位，因此负数会变成较大的正数

代码​

[l, r] 左右闭合写法​

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  const n = nums.length
  let l = 0
  let mid = 0
  let r = n - 1 // 闭合区间中 r 是包含，此时 nums.length 下标超出了数组的长度，需要-1

  // 假设区间为 [l, r],左右区间都是闭合的，因此有可能出现 l==r 这种情况
  while (l <= r) {
    mid = (l + r) >>> 1 // 这里相当于 ( l + r ) / 2 之后取整，确保最终 mid 还是整型

    if (nums[mid] === target) return mid

    if (nums[mid] > target) {
      // 不能设置 r = mid，已经明确 nums[mid] > target 即 此时的 mid 绝对不包含 target
      // 若重新将这个不符合的范围纳入循环，有可能引起死循环
      r = mid - 1
    } else {
      l = mid + 1
    }
  }
  return -1
}

[l, r) 左闭右开写法​

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  // 假设区间为 [l, r)
  let mid = 0
  let l = 0
  let r = nums.length // 此时右区间是不包含的，所以不需要减 1

  // 升序数组，[l, r) 区间，l == r 这种情况与区间定义相悖，因此循环条件为 l < r
  while (l < r) {
    mid = (l + r) >>> 1
    if (nums[mid] === target) return mid
    // 中位数与 target 的关系画图会更加清晰
    if (nums[mid] > target) {
      r = mid // 右区间是开合的，因此 mid 本身是不包含的，不需要减一排除
    } else {
      l = mid + 1
    }
  }
  return -1
}

取中位数的写法​

let mid = (l + r) >>> 1

/**
 * 法一：无符号右移操作符，相当于 l + r 除以 2 之后取整
 *
 * 优：避免溢出；效率上比数学运算更快（现代JS引擎差异微乎其微）
 *
 * 劣：可读性差，对于不熟悉位运算的开发者而言，不如数学运算直观
 */
let mid = Math.floor((l + r) / 2)

/**
 * 法二：计算平均值之后向下取整
 *
 * 优：可读性高，直观易理解
 *
 * 劣：l、r过大时有整数溢出风险；性能相对于位操作符略逊一筹（大多数情况下影响微乎其微）
 */
let mid = l + Math.floor((r - l) / 2)

/**
 * 法三：计算 r-l 中位数，再加上左区间
 *
 * 优：避免整数溢出；清晰：计算区间中位数，再加上左区间
 *
 * 劣：对比直接相加取中位数，稍显复杂
 */

总结​

选择使用哪种写法主要取决于以下几个因素：

  • 可读性：在团队中，选择更易读的写法可能更受欢迎，尤其是新手开发者。
  • 性能：在性能要求高的场景下，可能会倾向于使用位运算。
  • 避免溢出：如果担心 l + r 会导致溢出，使用 l + Math.floor((r - l) / 2) 是更安全的选择。

相关题目​