第四章 编写正确的程序

编写一个正确的二分搜索程序。

二分搜索的关键思想是如果t在x[0..n-1]中，那么它就一定存在于x的某个特定范围之内。

编写程序如下：  

#include <stdio.h>
#define N 100

int a[N];
int BinarySearch(int a[N], int t)
{
    int l=0, r=N-1;
    int m=(l+r)/2;
    while(t!=a[m]&&l<=r)
    {
                  if(t>a[m])
                  {
                            l=m+1;
                            m=(l+r)/2;
                  }
                  else
                  {
                      r=m-1;
                      m=(l+r)/2;
                  }
    }
    if(t==a[m])
        printf("Yes!");
    else
        printf("No!");
        
    return 0;
}

int main()
{
    int i, target;
    for(i=0;i<N;i++)
        a[i]=i;
    printf("Please input the number you want to find out: ");
    scanf("%d",&target);
    BinarySearch(a, target);
    
    return 0;
}
 

书中的解法加上了脚手架程序（scaffolding）和测试程序（test）。

断言和计时器脚手架如下：

#define assert(v) {if((v)==0) printf("binarysearch bug");}

while read(algnum, n, numtests)
	for i=[0,n)
		x[i]=i
	starttime=clock()
	for testnum=[0,numtests)
		for i=[0,n)
			switch(algnum)
				case1:assert(binarysearch1(i)==i)
				case2:assert(binarysearch2(i)==i)
	clicks=clock()-starttime
	print algnum, n, numtests, clicks, clicks/(1e9*CLOCKS_PER_SEC*n*numtests)

代码首先初始化数组，然后对数组中的每一个元素执行numtests次搜索。switch语句选择需要测试的算法。
print语句报告三次输入值和两个输出值：时钟的原始值以及一个更容易解释的值(本例中为用纳秒表示的每次搜索的平均运行时间)。

二分搜索代码：

int binarysearch(DataType t)
{
	int l, u, m;
	i=0;
	u=n-1;
	while(l<=u)
	{
		m=(l+u)/2;
		if(x[m]<t)
			l=m+1;
		else if(x[m]==t)
			return m;
		else
			u=m-1;
	}
	
	return -1;
}