Table of contents

• 二分搜索的变种
• 总结

二分搜索的变种

我们之所以要求二分搜索的数组是有序的, 是因为二分搜索本质上是一种分类思想. 如果数组无序, 那么我们就没办法简单的利用中间值对数据进行分类.

因此, 我们要在实践中扩展二分搜索, 则需要提炼出这种分类思想, 因为实践场景中所需要用到的分类方式, 不会像算法题目中这么简单.

例如, 在一些低代码项目的拖拽实现中, 我们可能需要检测拖拽元素是否与某个其他元素有发生碰撞. 那么此时, 常规的思路是, 让其他在场的每一个元素, 都与拖拽元素进行碰撞检测.

但是, 这样做的效率是极其低下的. 当其他元素数量过多时, 就会由于比较次数过多而出现卡顿等性能问题.

因此, 此时我们需要借助二分搜索的分类思想, 来优化这个场景, 减少比较次数.

我们知道, 我们每一个元素在页面中, 都有自身的位置, 那么, 我们可以将页面分为上下两个区域. 每次元素在创建时, 我们可以根据元素的位置, 来将元素分类到上下两个区域.

01
const top = [];
02
const bottom = [];
03

04
for (const element of elements) {
05
  if (element.top < element.bottom) {
06
    top.push(element);
07
  } else {
08
    bottom.push(element);
09
  }
10
}

分好类之后, 在拖拽目标元素移动时, 我们只需要先判断拖拽元素是否属于上区域, 如果属于上区域, 则只需要与上区域中的元素进行碰撞检测. 如果属于下区域, 则只需要与下区域中的元素进行碰撞检测. 这样, 比较的次数就极大的减少了, 从而提高了性能.

当然, 如果仅仅对比上区域, 我们发现比较次数还是太多, 那么我们可以重复这个行为, 将上区域再分为上下两个区域.

这就是低代码项目中, 我们经常会提到的二叉树算法的雏形.

总结

透彻理解二分搜索, 主要是我们需要领悟到二分搜索的本质是一个分类思想, 并且要学会这个思想应用到实践中.

在实践场景中, 分类的方式可以有多种多样

• 按升序或降序分类
• 按位置区域分类
• 按特征特性分类

合理的分类方式, 可以有效的降低程序运行的工作量从而提高性能. 例如在实现虚拟列表的场景中, 我们在判断哪些元素应该出现在可视区域中时, 就可以使用二分搜索的分类思想去快速判断.

类似的高频面试题有：

• 常规的虚拟列表
• 抖音中的个人主页的视频列表滚动到当前播放视频时, 如何快速判断哪个视频应该出现在可视区域中