Table of contents

• 二分搜索的变种
• 总结

二分搜索的变种

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

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

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

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

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

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

10
const top = [];
20
const bottom = [];
30

40
for (const element of elements) {
50
  if (element.top < element.bottom) {
60
    top.push(element);
70
  } else {
80
    bottom.push(element);
90
  }
10
}

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

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

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

总结

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

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

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

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

类似的高频面试题有：

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