有哪些事实没有一定计算机知识的人不会相信?
计算机 知识 哪些 没有 不会 一定 事实 相信
2023-09-11 14:13:58 时间
昨天在知乎看到一个热门话题:有哪些事实没有一定计算机知识的人不会相信?
我抖了一个机灵,把《编程珠玑》上关于二分查找法的梗答上去,一天之内挺多人留言点赞说没想到自己写不出完全准确的二分查找法,小丑竟然是我自己,根据评论数据来看,的的确确是九成的人无法写对,他们通过这个回答知道了自己以为知道但实际上不不知道的东西。
我觉得这个小知识或许对你有帮助,所以分享一下。
以下为我在该问题下的回答:
别说是没有计算机知识的人了,即使有也很多人不相信:给予他们充足时间的情况下,有百分之九十以上的人无法编写出完全准确的二分查找法的代码。
以上的结论来源于《编程珠玑》一书。
如果不信的话,可以先自己手写一遍,不想写的话,看看下方的代码,然后花一分钟思考,你觉得它哪里有问题?
public static int binary(int[] arr, int data) {
int min = 0;
int max = arr.length - 1;
int mid;
while (min <= max) {
mid = (min + max) / 2;
if (arr[mid] > data) {
max = mid - 1;
} else if (arr[mid] < data) {
min = mid + 1;
} else {
return mid;
}
}
return -1;
}
看出来了么?
3
2
1
揭晓答案,问题出在第 6 行代码处:
mid = (min + max) / 2;
这句代码在 min 和 max 很大的时候,会出现溢出的情况,从而导致数组访问出错。
别看现在轻描淡写的指出了这个错误,但这个错误在当时可是存在了好些年。
第一篇二分搜索论文是 1946 年发表,然而第一个没有 bug 的二分查找法却是在 1962 年才出现,中间用了 16 年的时间。
那怎么改进呢?一般的做法是这样的:将加法变成减法。
public static int binary(int[] arr, int data) {
int min = 0;
int max = arr.length - 1;
int mid;
while (min <= max) {
// 防止溢出
mid = min + (max - min) / 2;
if (arr[mid] > data) {
max = mid - 1;
} else if (arr[mid] < data) {
min = mid + 1;
} else {
return mid;
}
}
return -1;
}
还有一种更高逼格的写法,也是官方的二分搜索法的实现写法:使用位运算。
public static int binary(int[] arr, int data) {
int min = 0;
int max = arr.length - 1;
int mid;
while (min <= max) {
// 无符号位运算符的优先级较低,先括起来
mid = min + ((max - min) >>> 1);
if (arr[mid] > data) {
max = mid - 1;
} else if (arr[mid] < data) {
min = mid + 1;
} else {
return mid;
}
}
return -1;
}
今天是持续写作第 12 / 100 天。
如果你有想交流的话题,欢迎留言。
相关文章
- 判断远程计算机是否需要重新启动
- 1-1python预备知识-计算机基础知识
- 如何确认计算机的GPU配置
- 计算机视觉 图像形成 几何图形和变换
- Atitit 计算机的组成与设计 目录 1. 计算机系统是由硬件系统和软件系统两大部分组成。 1 1.1. Cpu(alu+cu )1 1.2. 存储内存 外村1 1.3. Io设备 鼠标
- 【数据结构与算法】编译原理基础知识 / 禅与计算机程序设计艺术 & ChatGPT
- 计算机毕设 SSM Vue的留学生交流互动管理系统(含源码+论文)
- 好书推荐:智能交通系统中的计算机视觉和成像
- 计算机安装ipguard客户端visual studio 2019报错build stopped:subcommand failed
- Java如何获取本地计算机的IP地址和主机名?
- 计算机组成原理期末救急--下
- 计算机的总线
- 如何确认计算机的GPU配置
- 计算机视觉的模型训练过程是什么?有哪些步骤?
- 投稿指南【NO.8】计算机学会CCF推荐期刊和会议分享(计算机体系结构/并行与分布计算/存储系统)
- 初识:计算机基础篇
- Win10 计算机入域后安装程序、打开重要设置都要输入域管理员密码才行
- 没有软件测试经验的计算机毕业生如何准备面试测试工程师这一职位?