20 年的 Bug ：几乎所有实现二分查找（Binary Search）和合并排序（Merge Sort）都有溢出漏洞！ 又一个-云头条
作者简介：Mohit Chawla是康奈尔大学的研究生。
一个20年来一直未被发现的bug！几乎所有实现的二分查找（Binary Search）和合并排序（Merge Sort）（又名“归并排序）都有问题！
有的人可能不知道二分查找是什么，因此有必要先解释一下：这是一种查找算法，使用分治（Divide & Conquer）模式来查找排序数组中的目标元素，时间复杂度为O（log n），其中“n”是指数组的大小。
所有程序员都使用二分查找，而且频繁使用！
下面是用C++实现的两种二分查找方法，两者只相差了一行，并排显示：
左图：原始算法，右图：修正后的算法
这两种算法都使用mid变量执行如下任务：
如果在当前的mid位置找到目标值香掉牙酥饼，终止查找。
通过将mid位置的值与目标值进行对比来缩小查找空间，将数组分成两半，因而在左半部分或右半部分中查找。
你有没有注意到第6行的区别？
所以幻世录1攻略，我们有两种方法来计算mid：
但是这个区别有什么影响呢？你可以在大量的手工测试用例上运行它，它仍然给出正确的答案，除非……
是的，你明白了问题所在！当low和high的总和超过231时，它就会溢出！
首先，不妨了解它如何会溢出：
假设你有一个大小为231-1的数组（有符号的32位整数的最大值）金古武侠赋，含有从1、2、3...到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圈人群，欢迎加入金敏书！
作者简介：Mohit Chawla是康奈尔大学的研究生。
一个20年来一直未被发现的bug！几乎所有实现的二分查找（Binary Search）和合并排序（Merge Sort）（又名“归并排序）都有问题！
有的人可能不知道二分查找是什么，因此有必要先解释一下：这是一种查找算法，使用分治（Divide & Conquer）模式来查找排序数组中的目标元素，时间复杂度为O（log n），其中“n”是指数组的大小。
所有程序员都使用二分查找，而且频繁使用！
下面是用C++实现的两种二分查找方法，两者只相差了一行，并排显示：
左图：原始算法，右图：修正后的算法
这两种算法都使用mid变量执行如下任务：
如果在当前的mid位置找到目标值香掉牙酥饼，终止查找。
通过将mid位置的值与目标值进行对比来缩小查找空间，将数组分成两半，因而在左半部分或右半部分中查找。
你有没有注意到第6行的区别？
所以幻世录1攻略，我们有两种方法来计算mid：
但是这个区别有什么影响呢？你可以在大量的手工测试用例上运行它，它仍然给出正确的答案，除非……
是的，你明白了问题所在！当low和high的总和超过231时，它就会溢出！
首先，不妨了解它如何会溢出：
假设你有一个大小为231-1的数组（有符号的32位整数的最大值）金古武侠赋，含有从1、2、3...到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圈人群，欢迎加入金敏书！