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

简介: 二分法大家都知道,记得应该是从初中学数学就学过,而在编程中也经常使用二分法来进行有序数列的查找。然而二分法并不紧紧局限于算法中的使用,他还被广泛使用于我们的工具中、数学中甚至生活中。

网络异常,图片无法展示
|

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

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

算法应用

算法中会使用二分法进行查找,然后使用两个索引来代表目标数据所可能在的范围,然后将数组从中间进行拆分,拿到中间数进行比对,即可根据数组的排序顺序、目标元素和中间数的大小比较,得出更小的比对区间,从而一次次缩小查找范围,在面对大数据时,可以有效的减少查找时间,提升查找效率,将事件复杂度缩小到 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 goodgit 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 个看起来一样的球里有一个重量比其它的重,有一个天平如何快速的找出不同的那颗球。

总结

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

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

相关文章
|
1天前
|
人工智能 自然语言处理 供应链
从第十批算法备案通过名单中分析算法的属地占比、行业及应用情况
2025年3月12日,国家网信办公布第十批深度合成算法通过名单,共395款。主要分布在广东、北京、上海、浙江等地,占比超80%,涵盖智能对话、图像生成、文本生成等多行业。典型应用包括医疗、教育、金融等领域,如觅健医疗内容生成算法、匠邦AI智能生成合成算法等。服务角色以面向用户为主,技术趋势为多模态融合与垂直领域专业化。
|
2天前
|
人工智能 自然语言处理 算法
从第九批深度合成备案通过公示名单分析算法备案属地、行业及应用领域占比
2024年12月20日,中央网信办公布第九批深度合成算法名单。分析显示,教育、智能对话、医疗健康和图像生成为核心应用领域。文本生成占比最高(57.56%),涵盖智能客服、法律咨询等;图像/视频生成次之(27.32%),应用于广告设计、影视制作等。北京、广东、浙江等地技术集中度高,多模态融合成未来重点。垂直行业如医疗、教育、金融加速引入AI,提升效率与用户体验。
|
6天前
|
存储 负载均衡 算法
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中,迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点,确保高效稳定的网络环境。该算法通过计算最短路径,提升数据传输速率与稳定性,实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用,为企业信息化建设提供有力支持。
37 15
|
8天前
|
存储 人工智能 算法
通过Milvus内置Sparse-BM25算法进行全文检索并将混合检索应用于RAG系统
阿里云向量检索服务Milvus 2.5版本在全文检索、关键词匹配以及混合检索(Hybrid Search)方面实现了显著的增强,在多模态检索、RAG等多场景中检索结果能够兼顾召回率与精确性。本文将详细介绍如何利用 Milvus 2.5 版本实现这些功能,并阐述其在RAG 应用的 Retrieve 阶段的最佳实践。
通过Milvus内置Sparse-BM25算法进行全文检索并将混合检索应用于RAG系统
|
13天前
|
运维 监控 算法
监控局域网其他电脑:Go 语言迪杰斯特拉算法的高效应用
在信息化时代,监控局域网成为网络管理与安全防护的关键需求。本文探讨了迪杰斯特拉(Dijkstra)算法在监控局域网中的应用,通过计算最短路径优化数据传输和故障检测。文中提供了使用Go语言实现的代码例程,展示了如何高效地进行网络监控,确保局域网的稳定运行和数据安全。迪杰斯特拉算法能减少传输延迟和带宽消耗,及时发现并处理网络故障,适用于复杂网络环境下的管理和维护。
|
14天前
|
存储 缓存 监控
企业监控软件中 Go 语言哈希表算法的应用研究与分析
在数字化时代,企业监控软件对企业的稳定运营至关重要。哈希表(散列表)作为高效的数据结构,广泛应用于企业监控中,如设备状态管理、数据分类和缓存机制。Go 语言中的 map 实现了哈希表,能快速处理海量监控数据,确保实时准确反映设备状态,提升系统性能,助力企业实现智能化管理。
28 3
|
15天前
|
算法 安全 Java
探讨组合加密算法在IM中的应用
本文深入分析了即时通信(IM)系统中所面临的各种安全问题,综合利用对称加密算法(DES算法)、公开密钥算法(RSA算法)和Hash算法(MD5)的优点,探讨组合加密算法在即时通信中的应用。
17 0
|
23天前
|
算法 安全 网络安全
基于 Python 的布隆过滤器算法在内网行为管理中的应用探究
在复杂多变的网络环境中,内网行为管理至关重要。本文介绍布隆过滤器(Bloom Filter),一种高效的空间节省型概率数据结构,用于判断元素是否存在于集合中。通过多个哈希函数映射到位数组,实现快速访问控制。Python代码示例展示了如何构建和使用布隆过滤器,有效提升企业内网安全性和资源管理效率。
50 9
|
24天前
|
机器学习/深度学习 人工智能 自然语言处理
解锁机器学习的新维度:元学习的算法与应用探秘
元学习作为一个重要的研究领域,正逐渐在多个应用领域展现其潜力。通过理解和应用元学习的基本算法,研究者可以更好地解决在样本不足或任务快速变化的情况下的学习问题。随着研究的深入,元学习有望在人工智能的未来发展中发挥更大的作用。
|
24天前
|
算法 Serverless 数据处理
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
47 12

热门文章

最新文章