二分法，不止是算法 - 你可能不知道的二分法应用

二分法大家都知道，记得应该是从初中学数学就学过，而在编程中也经常使用二分法来进行有序数列的查找。

然而二分法并不紧紧局限于算法中的使用，他还被广泛使用于我们的工具中、数学中甚至生活中。

算法应用

算法中会使用二分法进行查找，然后使用两个索引来代表目标数据所可能在的范围，然后将数组从中间进行拆分，拿到中间数进行比对，即可根据数组的排序顺序、目标元素和中间数的大小比较，得出更小的比对区间，从而一次次缩小查找范围，在面对大数据时，可以有效的减少查找时间，提升查找效率，将事件复杂度缩小到 O(log2(n))。不过二分法也存在一定局限性，必须要数组是有序的。

可以大概看一下实现，一段平平无奇的二分查找代码：

export const binarySearch = (arr: number[], target: number): number => {
    const len = arr.length;
    if (!len) return -1;
    let startIndex = 0;
    let endIndex = len - 1;
    while (startIndex <= endIndex) {
        let midIndex = ((startIndex + endIndex) / 2) | 0;
        let midTarget = arr[midIndex];
        if (target === midTarget) return;
        target < midTarget ? (endIndex = midIndex - 1) : (startIndex = midIndex + 1);
    }
    return -1;
};
复制代码

当然，上面只是顺带提过，并非本文的重点，下面说下二分法在非算法领域的应用，看看它的应用之广泛，可能超乎你的想象。

Git 中的二分法

git 中就存在二分法的另一种应用：git bisect。当我们代码上线后突然有一天一个最近根本没改动的模块出现问题了，一般会很难定位问题是由哪次改动引起的。这是便可以使用 git bisect 进行帮助定位。要启动我们一般会指定一个起点 hash，终点一般就是当前 HEAD。

git bisect start HEAD HEAD~10
复制代码

git 会切换到 HEAD~10 的 commit 上，此时你可以查看当前版本是否存在该 bug，然后根据存在结果判定输入 git bisect good 或 git bisect bad。git 便会自动在 bad 范围中进行二分，缩小查找范围，直到最终确定最先出现 bug 的 commit：a819d21 is the first bad commit。

借助 git bisect 可以在 bug 不明确时快速定位到初次导致 bug 的 commit，便可借助当次 commit 中的修改，快速定位到引起 bug 的原因。

VSCode 中的二分法

而在 VSCode 中，二分法也同样有着类似的用途。VSCode 作为一代轻量级 IDE 新秀，虽然功能已经非常丰富，但是对比一些专业的 IDE 在很多功能上还是有所欠缺。所以开发者都会使用大量插件来弥补这些功能。然而插件五花八门，质量参差不齐，很容易就会出现一些插件导致内存泄漏、CPU 爆满的情况。所以在这种情况下就需要一个个禁用插件来排查到底是什么插件导致的问题。于是乎 VSCode 中也出现了自带的二分法定位问题插件的功能。

要启动该功能，只需要启动 VSCode 命令输入 Extension Bisect，也可在插件菜单中启动。

启动后 VSCode 提示本次可能需要的次数等说明，确定后便会将插件进行拆分禁用，然后在右下角询问当前情况是否正常（可能需要手动点击右下角消息提示打开）。

从而一次次缩小范围，定位到引起问题的插件。

除了定位插件的 bug，你也可以借助它来定位插件的功能，比如你很好奇某个 snippet 是哪个插件提供的，同样可以借助它来定位。

BUG 定位中的二分法

除了上述工具自带的这些应用了二分法的工具，我们在实际编程过程中同样可以借助二分法来定位 bug。

通常修 bug 时最难的不是改代码，而是定位代码。首先必须要知道导致 bug 的代码位置才能修复它。所以日常遇到 bug 却毫无头绪时，二分法可以非常无脑的帮你缩小需要排查的范围。

除了上面的 git bisect，我通常还会通过代码分割来进行代码定位，比如一个页面上有多个模块，此时便可将模块进行去除，然后查看 bug 是否消除来不断判定缩小查找范围，从而最终定位。又比如页面中的样式出现无法理解的情况，也可以通过将生效的样式、嵌套位置等进行二分来进行原因定位。

生活中的二分法

除了上述在编程中的二分法使用，我们在生活中也可以使用二分法来解决问题。

比如发布文字到网上遇到 SC，死活通不过而自己又找不到失败的原因，就可以使用二分法分段尝试定位。比如数据上传过大，又不知道上传多大的数据包合适，可以通过二分法尝试出合适的大小。比如和小朋友玩游戏，抽一张扑克牌、或写一个数字，然后看看谁能更快的猜到数字是多少。比如一些有意思的数学题，100 个看起来一样的球里有一个重量比其它的重，有一个天平如何快速的找出不同的那颗球。

总结

二分法是一种很常见的方法，他的本质是通过判定查找目标是否在某个范围内，然后不断对范围进行拆分定位，从而进行批量的筛除，达成查找的目的。只要在能够判定目标范围的情况下，二分法都能发挥出不错的效果。除了二分法，还可以使用三分法等其它衍生的方案，其本质是想通的。如果大家还知道哪些关于二分法的使用案例，欢迎留言。

在生活中同样可以使用二分法，不过在专业领域个人觉得还是要以思考为优先，能够直接动脑的就不要"动手"，毕竟二分法就是一种试错法（比依次试错好一丢丢的那种），产生依赖很容易丢失自己的思考能力。🤦‍♂️ 在一些非专业领域，或者丧失思考能力的情况下还是很推荐的。🐶