注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TOTO

Think and Be Different

 
 
 

日志

 
 

二分查找的bug[zz]  

2007-06-04 11:18:44|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 

http://pprun.blogspot.com/2007/05/bug.html【文章原地址】

大概是在去年的七月份左右,我首先在 javalobby 上看到这篇。当时也无比震惊,因为JDK (1.5及之前的版本) 中 Arrays.binarySearch(int[] a, int key) 及 Collections.binarySearch(int[] a, int key) (其调用indexedBinarySearch) 存在一个在业界隐藏了几十年的BUG,而这两个方法的作者恰恰是两位高人实现:

* @author Josh Bloch
* @author Neal Gafter

我想在Java 领域呆的比较长的开发者应该会有所耳闻吧,Josh Bloch 被称之为 "Java 之母"(虽然他是一位男性),因为 java collection 框架,java.math, 泛型 及《Effective Java Programming Language Guide》都出自他之手;而 Neal Gafter 则是 我们每天都用的JAVA编译器 Javac 的实现者。


我们先看有问题的代码:


public static int binarySearch(int[] a, int key) {
int low = 0;
int high = a.length-1;

while (low <= high) {
int mid = (low + high) >> 1;
int midVal = a[mid];

if (midVal < low =" mid"> key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}

有问题的代码是这一行:
int mid = (low + high) >> 1; 

大家知道,其等价于:
int mid =(low + high) / 2;

问题是在 low 和 high 都很大时,比如数组的元素达到 2^30 时,low + high 将超过整数的最大值 2^31 -1,此时将造成溢流,溢流后得到的 mid 为负值。

正确的实现应该为:
             int mid = low + ((high - low) / 2);

或者更加清楚地使用Java的无符号右移操作符:
            int mid = (low + high) >>> 1;

虽然这个问题目前得到解决,我们就能断定这十几行程序就准确无误吗?
但连以上两位作者目前也还表示怀疑。
从行内得知,第一个二分法算法是1946年出现的,而当时被认为“无误”的实现到1962年才出现(也就是说以上十几行代码是经过十几年才得到的)。因为当时的数据量不可能逼近 2 ^ 30的数量级,所以直到去年这个BUG被提交到
Java 的 Bug 库中。可想人类的思维是有缺陷的。

目前,对于搜索引擎,基因工程领域,这一数量级应该是少见多怪了,所以如果你工作的领域需要处理大量的数据时,请使用 JDK 6.0

顺便提一句,对于C的实现,可以采用如下实现:
mid = ((unsigned) (low + high)) >> 1;
看到这样的情况,作为程序员,我们应该时刻警惕、保持低调!
  评论这张
 
阅读(897)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017