微信号:YunTouTiao

介绍:云计算领域科技媒体:传播观点,传播价值;Web:www.yuntoutiao.com ,欢迎互动~~~

又一个 20 年的 Bug :几乎所有实现二分查找(Binary Search

2018-01-07 22:54 云头条

作者简介:Mohit Chawla是康奈尔大学的研究生。


一个20年来一直未被发现的bug!几乎所有实现的二分查找(Binary Search)和合并排序(Merge Sort)(又名“归并排序)都有问题!

 

有的人可能不知道二分查找是什么,因此有必要先解释一下:这是一种查找算法,使用分治(Divide & Conquer)模式来查找排序数组中的目标元素,时间复杂度为O(log n),其中“n”是指数组的大小。


所有程序员都使用二分查找,而且频繁使用!


下面是用C++实现的两种二分查找方法,两者只相差了一行,并排显示:


左图:原始算法,右图:修正后的算法


这两种算法都使用mid变量执行如下任务:


  • 如果在当前的mid位置找到目标值,终止查找。

  • 通过将mid位置的值与目标值进行对比来缩小查找空间,将数组分成两半,因而在左半部分或右半部分中查找。


你有没有注意到第6行的区别?


所以,我们有两种方法来计算mid:



但是这个区别有什么影响呢?你可以在大量的手工测试用例上运行它,它仍然给出正确的答案,除非……


是的,你明白了问题所在!当low和high的总和超过231时,它就会溢出!


首先,不妨了解它如何会溢出:


假设你有一个大小为231-1的数组(有符号的32位整数的最大值),含有从1、23...到231-1的元素(按增加的顺序)。假设target(有待查找的元素)是231-2(倒数第二个元素):



在第一次迭代中,你计算



可以看到如下的mid和target:



然而,由于target (231-2)在数组的右半部分,所以我们设置



于是,查找空间缩减至数组的第二半:



现在,在第二次迭代中,我们计算新的mid为:



由于总和超过231,结果导致溢出。这将导致不可预知的结果。(请参阅下面的执行追踪)


左图:第二次迭代中出现溢出,右图:修正后的算法的输出结果


这就是二分查找中那个知名的“溢出漏洞”,20多年来这个漏洞一直未被发现(https://en.wikipedia.org/wiki/Binary_search_algorithm)!!!



连Java在java.util.Arrays中的二分查找也存在同样的缺陷,直到报告给Sun公司,并于2006年得到修补。


那么,如何修补这个漏洞呢?


我们已经看到:



一种更快的实现方法是(在这种特殊情况下):



其中,>>>是无符号右移运算符。


在C/CPP中没有>>>,可以使用下面这个:



这个二分查找缺陷同样适用于合并排序及其他分治算法。所以,如果你之前不知道这个,现在修补你实现的代码是明智之举。


其次,我们忽略了什么?大多数博客错过了什么?务实的分析。


忽略了这一点:


我们是否被允许分配大小为231的数组?这种问题会出现在现实生活的系统中吗?


内存分配:


观察到一个大小为231的整数数组将需要8GB内存。


针对Java:


结果证明,你可以创建一个大小为231 -1的数组(或大得足以让溢出条件发生的数组)。


针对C++:


当然,你无法在堆栈上静态地分配那么多的内存(你会看到运行时错误,由于超过默认的堆栈大小,通常是1-8 MB,导致你的程序崩溃),但是可以在堆区上分配那么多的内存。所以,溢出缺陷情况仍可能会出现在C++中。


从理论上来说,如果数组大小大于231,比如说232,那么在这种情况下,你就需要使用64位整数,但在263这个临界点又会出现同样的溢出缺陷情况。实际上,这样大小的数组通常不是更可取的,因为之后很难将这么大的数组装入到内存中。


所以,这种情况可能会出现,具体取决于如今系统的使用情况和规模。因此,编写代码实现分治算法(比如二分查找)时建议考虑到这种情况。


简而言之:


  • 所有分治算法都容易受到这类缺陷的影响。

  • 修补你实现的代码,如果它是某个库的一部分,因而会获得异常大的数组的输入更要修补。


相关阅读:

中高端IT圈人群,欢迎加入!


 
云头条 更多文章 Intel x86 肯定会完蛋:以云为中心的未来依赖开源芯片! Intel CPU bug 和调戏小秘书,原来还有类似之处 ? 习大大在读《终极算法:机器学习和人工智能如何重塑世界》、《智能浪潮:增强时代来临》这两本 AI 方面的书 Intel CPU 曝大 BUG:迫使重新设计 Linux 和 Wi AI 的 2017
猜您喜欢 移动开发者的冬天真的来了 嵌入式调试器原理和各类调试器集锦 Spark 1.0 跳票? 【重磅】拿什么应对 AlphaGo?中国版 DARPA 蓄势待发 [职业生涯] 技术反思