关于binary search
2023-03-14 10:20:43 时间
编程珠玑Column 4关于binary search的部分相当精彩,1946年就有人发表binary search,但直到1962第一个正确运行的算法才写出来。尽管算法描述看起来简单明了,但是要写的正确却是有许多地方要仔细考虑。作者着重强调的是对程序正确性的分析方法,仔细分析方法的pre-condition, invariant,和post-condition。g9老大翻译过Joshua Bloch在google blog上的文章《号外,号外,几乎所有的binary search和mergsort都有错》,原文在这里。今天看了下原文,有更新,对于求中值索引的c/c++方法原文仍然是有错的,本来是这样:
但是在c99标准中,对于两个signed数值之和,如果溢出结果是未定义的(undefined),也就是说与编译器实现相关。上面的代码应该修改为:
我查了下jdk6的java.util.Arrays的源码,joshua bloch说的这个问题已经解决,现在的binary search如下:
int mid = ((unsigned) (low + high)) >> 1。
但是在c99标准中,对于两个signed数值之和,如果溢出结果是未定义的(undefined),也就是说与编译器实现相关。上面的代码应该修改为:
mid = ((unsigned int)low + (unsigned int)high)) >> 1;
我查了下jdk6的java.util.Arrays的源码,joshua bloch说的这个问题已经解决,现在的binary search如下:
// Like public version, but without range checks.
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
如原文所讨论的,采用了>>>操作符替代除以2
文章转自庄周梦蝶 ,原文发布时间2008-04-02
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的