专栏首页TechFlow算法浅谈——人人皆知却很多人写不对的二分法

算法浅谈——人人皆知却很多人写不对的二分法

点击上方蓝字,和我一起学技术。

1

二分法可以说是鼎鼎大名,哪怕是没有学过编程的同学,也许说不上来二分法这个名字,但是对于其中的精髓应该都是有所了解的。不了解的同学也没关系,我一句话就能交代清楚:我们每次将一个集合一分为二,每次舍弃其中一半。

早在两千多年前,庄子就搞清楚了二分法的精髓,他说:一尺之棰,日取其半,万世不竭。从这个角度来说,二分法可能是这个世界上最古老的算法之一了。

二分法不仅古老,而且在计算机系统当中非常常见,许多系统当中都用到了二分法的思想。除此之外,在面试的时候,二分法的算法题也是常客。因为二分法本身不复杂,几乎人人都会,但是对二分法的使用能力却各有不同。出二分法的题,可以真实考察面试者的算法能力和编程功底。

不说比较困难的算法题想不出思路,就说最简单没有任何难度的纯二分,在面试的时候,出错的写出bug的也大有人在。

很多人会觉得奇怪,二分法这么简单的算法,真的有人写不出来吗?

还真的有,原因也很简单,恰恰就是二分法太简单了。

无论是在算法导论还是在一些其他的算法教材当中,关于二分法的描述都不多,详细的会有一些图例展示一下二分法的思想,简单的就用几句话描述一下原理,最后再展示一下代码,就完事了。读者在学的时候也是一样,看了一眼原理,哦,非常简单,再看一眼代码,只有三四行,差不多一眼就能记住,那就丢在一边吧。到了真正上手的时候,问题一下就暴露了出来。

二分法最常见的问题有两个,一个是二分的区间边界不清楚,另一个是二分查找的结果不明确。我想,这两个问题是前几次实现二分法的时候,一定会遇到的。遗憾的是,目前的教材当中对于这两个问题介绍都不多,都只有代码,留给读者自行揣摩。

2

我们先说第一个问题——边界

早在小学我们就学过,用l表示区间左边界,r表示区间右边界,mid=(l + r) / 2表示二分的中间点。这个在数学里非常明确,但在编程的时候,有一个隐藏的问题被忽略了。究竟这个区间是闭区间呢,还是开区间呢,还是半开半闭区间或者是半闭半开区间?如果这个问题不想清楚,想要一次性写出没有bug的代码,老实说很不容易。

首先,二分终止的条件究竟怎么写,是while (l < r) 还是 while (l <= r) 还是别的?还有,在搜索的时候,我们究竟要不要将a[mid] == v的情况单独判断?我们是判断a[mid] < v还是a[mid] <= v?假设我们选择用a[mid] <= v,得到的结果为true。我们知道答案应该在区间的右半边,我们需要舍弃左边的区间。应该对l赋值,但是我们是赋值成l = m呢还是l=m + 1呢?又是为什么呢?

你看,如果l和r表示的区间不考虑清楚,我们在实际写代码的时候就会遇到这样棘手的问题。坑爹的是,当我们为这些边界头疼的时候,我们并不能意识到这是因为我们没有搞清楚表示区间的方法导致的。往往会觉得是自己不够熟悉。

显然,要解决这个问题需要确定l和r表示的区间种类。那么到底应该选择什么区间呢?是左闭右开,还是全闭,还是左开右闭呢?

答案有点出人意料,都行

理论上来说,不论选什么样的区间,只要代码得当,都是可以的,可以说是完全看个人喜好。不过我个人推荐左闭右开,原因很简单,这个和编程当中的数组定义的情况一致。我们都知道,在代码的世界里,数组是从0开始的,一个长度为10的数组,最后一个元素的下标是9。如果使用左闭右开区间,我们将l=0,r=数组长度,就完成了初始化,如果用闭区间,r=长度-1,不免显得有些多余。

假设我们确定了使用左闭右开区间,我们再来看前面说的两个问题。

区间确定了,终止条件也就明确了,左闭右开区间[l, r)不为空的话,r 至少大于等于l + 1。我们要在区间长度大于1的时候执行二分,所以二分的循环条件应该是while (l + 1 < r)。

3

那么while里的判断条件呢?

我们列举一下,a[mid] 和v的大小关系无非只有三种。

第一种a[mid] = v,很简单,mid就是我们要查找的结果,直接返回。

第二种a[mid] < v,说明我们应该取右边的区间,由于l的位置可以取到,而mid已经不是答案了,所以l = mid + 1。

第三种a[mid] > v,应该取左边的区间,mid不是答案,但是由于r指向的位置本身就不在候选区间里,所以r = mid,而不是mid-1,因为mid-1可能是答案,而r处的位置是取不到的。

到这里,似乎一切完美,我们可以很顺利地写出代码了。但是还没有结束,依然还有一个小问题。

前文说了,a[mid]和v的关系有三种,当a[mid] = v的时候,我们就找到了答案。从这个角度来看,我们二分的时候,通过l和r缩小区间的范围,通过mid来寻找答案。但是既然我们已经折半区间的大小了,那么当区间长度为1的时候,剩下的就是答案,我们为什么还需要通过mid去查找答案呢?如果我们就想通过区间本身来查找答案,那么应该怎么办呢?

也不难,我们需要把a[mid]小于和等于v的两种情况合并,由于a[mid]可能等于v,所以我们不能跳过mid这个位置,l = mid + 1 应该写成l = mid,于是整个代码也就出来了:

  1. def binary_search(a, v):
  2. l, r = 0, len(a)
  3. while l + 1 < r:
  4. m = (l + r) // 2
  5. if a[m] <= v:
  6. l = m
  7. else:
  8. r = m
  9. # 通过a[l] == v判断v不存在与a数组当中的情况
  10. return l

4

可能会有同学好奇,如果我不使用左闭右开,而使用闭区间呢,代码又该怎么写?

其实只要把区间想清楚了,写出来也不难。

  1. def binary_search(a, v):
  2. l, r = 0, len(a) - 1
  3. while l <= r:
  4. m = (l + r) // 2
  5. if a[m] == v:
  6. return m
  7. if a[m] < v:
  8. l = m + 1
  9. else:
  10. r = m - 1
  11. # 表示不存在
  12. return -1

不过还有一个小问题,为什么闭区间形式的二分法的判断推荐是while (l <= r)呢?换成while (l < r)行不行?这个问题就留给大家思考。

二分法虽然简单,但这些细节都理解清楚也并不容易,在算法领域当中,如果细节没有理解到位,阴沟里翻船是非常平常的事情。希望今天的文章能对大家有所帮助。

本文分享自微信公众号 - TechFlow(techflow2019),作者:梁唐

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Golang | 既是接口又是类型,interface是什么神仙用法?

    在上一篇文章当中我们介绍了面向对象的一些基本概念,以及golang当中interface和多态的实现方法。今天我们继续来介绍interface当中其他的一些方法...

    TechFlow-承志
  • 算法浅谈——走迷宫问题与广度优先搜索

    我们都知道,工业上的很多问题经过抽象和建模之后,本质还是数学问题。而说到数学问题就离不开方程,在数学上我们可以用各种推算、公式,但是有没有想过在计算机领域我们如...

    TechFlow-承志
  • Python元类实战,动手实现数据库ORM框架

    今天是Python专题的第19篇文章,我们一起来用元类实现一个简易的ORM数据库框架。

    TechFlow-承志
  • 零基础Python教程039期 重修列表基本操作

    上一节中,我们对python的循环控制语句做了基本的练习,也掌握了一些技巧。本节开始,我们继续新的知识点。

    刘金玉编程
  • 软件设计七大原则实战(四)-单一职责原则1 定义2 特点3 优点

    单一职责原则的英文名称是Single Responsibility Principle,简称是SRP。这个设计原则备受争议,只要你想和别人争执、怄气或者是吵架,...

    JavaEdge
  • vmware 扩展分区大小

    tanmx
  • 2018 年你可能已经错过的 Java 类库

    因为内容非常好,我便将它整理成参考列表分享给大家, 同时附上各个库的特性简介和示例。

    凯哥Java
  • PyQt 键盘事件和鼠标事件

    PyQt为事件处理提供了两种机制:高级的信号和槽机制,以及低级的事件处理程序。前者已经介绍过,后者也有涉及,比如我们曾重新实现过窗口部件的closeEvent(...

    用户6021899
  • c++ 头文件

    可以将程序分为二部分: 头文件:包含结构声明和使用这些结构的函数的原型 源代码文件: 包含与结构有关的函数的代码 不要将函数的定义或变量的声明放在头文件里, 一...

    lpxxn
  • 手把手教您构建自己的 DevOps 流水线

    持续交付是一组能够帮助软件开发团队极大的提高其软件交付的速度和质量的模式和最佳实践组成。

    DevOps时代

扫码关注云+社区

领取腾讯云代金券