90%程序员写不出无BUG的二分查找程序?
相关文章链接如下:
《编程珠玑》(第二版)一书第四章中提及过100多名专业程序员使用两个小时的充足时间编写一个简单的二分查找程序,结果发现90%的人编出的代码都有BUG,Knuth也在他的《Sorting and Searching》一书中提过,第一个二分查找程序在1946年已经公布,但是到了1962年才出现第一个没有BUG的二分查找程序,期间经历了16年的时间。那么为什么一个简单的二分查找程序会这么容易出错呢?看一看有序表的查找的测试用例设计也许能明白为什么。
要对有序表查找进行用例设计,我们可以先分析输入域,实际上有两个输入域,一个是要查找的数据,另外一个是有序表,可以先对有序表数据的个数进行分类,有序表中可能有0,1,2,3,…个数据。因此我们可以将目标数据分为以下几个类:
完成第1级分类后,我们可以再对数据的特点进行分类,因为有序表是一个有顺序的表,是有大小顺序的,因此可以根据数据特点再进行分类,以3个数据为例可以进行以下分类:
有序表有0、1、2、4个以上数据的情况都可以按照以上的类似的方式进行再分类。
当按有序表中分类好后,可以再按要查找的数据进行分类
当对查找的数据和有序表分别分好类后,就可以把这两种分类组合起来,比如将有序表有3个数据的分类情况和查找数据的分类情况组合起来就可以得到以下的分类:
组合完后,还需要将一些不可能或不需要的组合删除掉,比如在3个数据都相等的情况下,查找数据介于集合两个相邻数据之间的情况就不存在,需要删除掉这种情况,查找数据在有序表中的3种分类也由于集合中数据都相等而变成了一个分类,下图便是3个数据都相等情况下的一个分类:
这样7个最终分类减少到只有4个最终分类,查找数据为空的情况并不是所有情况下都需要测试的,其实只要测试有序表中有数据和没有数据两种情况就够了,因此查找数据为空的情况如果在其他情况中有了分类,那么也可以将其删去,这样3个数据都相等的情况就只有3个最终分类,如下图所示:
有序表有0个数据时可以所见成测试两种情况,一种是查找的数据为空,一种是查找的数据不为空。
有序表中有1个数据时的分类可以缩减成以下3种分类情况:
有序表中有2个数据的分类可以缩减成以下8种分类:
这样一来,即使不考虑4个以上数据以及3个数据在有两个数据相等情况下的分类,总共的最终分类也有20多种,每种分类至少需要设计一个测试用例,总共至少需要20多个测试用例,一个简单的二分查找的测试用例都至少需要20多个,看到这里大家也许会明白为什么90%的专业程序员写不出一个无BUG的二分查找程序来。
分享到:
相关推荐
90%程序员写不出无BUG的二分查找程序?.rar
1.开会 2.回复所有的电子邮件 3.衡量生产能力 5.“以后再修复”思维模式即“技术债务” 6.非程序员经理 7.程序员经理 8.技术过硬但有些强势的程序员
《算法导论》是一本好书,但是他太难了,就算是现在的我,再不借助资料的情况下,也绝看不...超四十种常见算法思想:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。
不管是用C/C++/Java等代码编写的程序,还是SQL编写的数据库脚本,都存在一个持续优化的过程。...下面这篇文章主要给大家总结介绍了90%程序员在面试的时候会遇到的索引优化问题,需要的朋友可以参考下。
要判断一个程序员是不是好的程序员,主要看他写的代码,因为程序员最重要的事是写代码。 即便不去理解代码的意图,只要看一眼,好的程序员写的代码与差的程序员写的代码基本上就可以看出来。好的程序员写的代码,...
程序员表白专用
为什么程序员必须写技术博客_以及如何写_博客在面试时的加分可不是一点点,别再犹豫了,快行动起来!
程序员写的后台模板,偷懒,采用mvc3的模式,图片均是来从网络,觉得不好看的可以替换。没有静态化。c#程序员可做参考用。
这是我为自己写的一款表白的程序,并且己用它表白成功,于是几经努力把它完成为一个完整的程序,这是我准备完成的程序之爱系列第一辑,希望能多做几辑吧。
程序员如何写文档
程序替换查找工具 内有:程序替换查找工具.EXE,文本查找替换专家.exe 特别适用服务器批量修改查找。
程序员交接文档!IT项目交接文档概要
《JavaWeb程序设计任务教程》一书源代码,中国工信出版社出版,黑马程序员编著,传智播客旗下高端教育品牌“黑马程序员”项目实战配套用书
程序员第二步从程序员到项目经理 程序员第二步从程序员到项目经理 程序员第二步从程序员到项目经理
二分法数据查找C语言实现,只有10%程序员能正确实现二分查找算法--http://news.csdn.net/a/20100423/218099.html
二分查找使用php快速的进行文件二分查找源码.zip使用php快速的进行文件二分查找源码.zip使用php快速的进行文件二分查找源码.zip使用php快速的进行文件二分查找源码.zip使用php快速的进行文件二分查找源码.zip使用php...
程序员写给火影迷,喜欢火影的朋友,可以看看这个3D相册,资源图片好像有点大了,如果不满意的朋友,可以自己更改里面的图片,希望对你有帮助。
全面介绍高级程序员编程方法~
程序员表白专用程序源码 (demo)程序员表白专用程序源码 (demo)程序员表白专用程序源码 (demo)程序员表白专用程序源码 (demo)程序员表白专用程序源码 (demo)程序员表白专用程序源码 (demo)程序员表白专用...