《编程珠玑》(第二版)一书第四章中提及过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个数据都相等情况下的一个分类: