震惊！几乎所有二分查找和归并排序都存在bug
2025-01-11
谷歌软件工程师Joshua Bloch爆料，一个潜伏了近二十年的二分查找算法bug，竟然出现在JDK和Jon Bentley的《编程珠玑》中！这个bug源于`int mid = (low + high) / 2;`这行代码，当`low`和`high`之和超过最大正整数时会发生整数溢出，导致数组越界。这个bug在数据量巨大的情况下才会暴露，在如今的大数据时代尤为致命。文章还讨论了多种修复方法，并强调了即使经过严格测试和证明，代码中仍然可能存在难以发现的bug，告诫程序员要保持谨慎和谦逊。