如果不是从一组随机的序列里查找，而是从一组排好序的序列里找出某个元素的位置，则可以有更快的算法：

#include <stdio.h>

#define LEN 8
int a[LEN] = { 1, 3, 3, 3, 4, 5, 6, 7 };

int binarysearch(int number)
{
	int mid, start = 0, end = LEN - 1;

	while (start <= end) {
		mid = (start + end) / 2;
		if (a[mid] < number)
			start = mid + 1;
		else if (a[mid] > number)
			end = mid - 1;
		else
			return mid;
	}
	return -1;
}

int main(void)
{
	printf("%d\n", binarysearch(3));
	return 0;
}

由于这个序列已经从小到大排好序了，每次取中间的元素和待查找的元素比较，如果中间的元素比待查找的元素小，就说明“如果待查找的元素存在，一定位于序列的后半部分”，这样可以把搜索范围缩小到后半部分，然后再次使用这种算法迭代。这种“每次将搜索范围缩小一半”的思想称为折半查找（Binary Search）。思考一下，这个算法的时间复杂度怎么表示？

这个算法的思想很简单，不是吗？可是[编程珠玑]上说作者在课堂上讲完这个算法的思想然后让学生写程序，有90%的人写出的程序中有各种各样的Bug，读者不信的话可以不看书自己写一遍试试。这个算法容易出错的地方很多，比如mid = (start + end) / 2;这一句，在数学概念上其实是mid = ⌊(start + end) / 2⌋，还有start = mid + 1;和end = mid - 1;，如果前者写成了start = mid;或后者写成了end = mid;那么很可能会导致死循环（想一想为什么）。

怎样才能尽可能保证程序的正确性呢？在第 2 节 “插入排序”我们讲过借助Loop Invariant检验循环的正确性，binarysearch这个函数的主体也是一个循环，它的Loop Invariant可以这样描述：待查找的元素number如果存在于数组a之中，那么一定存在于a[start..end]这个范围之间，换句话说，在这个范围之外的数组a的元素中一定不存在number这个元素。以下为了书写方便，我们把这句话表示成mustbe(start, end, number)。可以一边看算法一边做推理：

int binarysearch(int number)
{
	int mid, start = 0, end = LEN - 1;

	/* 假定a是排好序的 */
	/* mustbe(start, end, number)，因为a[start..end]就是整个数组a[0..LEN-1] */
	while (start <= end) {
	/* mustbe(start, end, number)，因为一开始进入循环时是正确的，每次循环也都维护了这个条件 */
		mid = (start + end) / 2;
		if (a[mid] < number)
			/* 既然a是排好序的，a[start..mid]应该都比number小，所以mustbe(mid+1, end, number) */
			start = mid + 1;
			/* 维护了mustbe(start, end, number) */
		else if (a[mid] > number)
			/* 既然a是排好序的，a[mid..end]应该都比number大，所以mustbe(start, mid-1, number) */
			end = mid - 1;
			/* 维护了mustbe(start, end, number) */
		else
			/* a[mid] == number，说明找到了 */
			return mid;
	}
	/* 
	 * mustbe(start, end, number)一直被循环维护着，到这里应该仍然成立，在a[start..end]范围之外一定不存在number，
	 * 但现在a[start..end]是空序列，在这个范围之外的正是整个数组a，因此整个数组a中都不存在number
	 */
	return -1;
}

注意这个算法有一个非常重要的前提－－a是排好序的，如果没有了这个前提，“如果a[mid] < number，则a[start..mid]应该都比number小”这一步推理就不成立。从更普遍的意义上说，调用者（Caller）和被调用者（或者叫函数的实现者，Callee）之间订立了一个契约（Contract），在调用函数之前，Caller需要对Callee尽到某些义务，比如确保a是排好序的，确保a[start..end]都是有效的数组元素而没有访问越界，这称为Precondition，然后在Callee中对一些Invariant进行维护（Maintenance），这些Invariant保证了Callee在结束时能够对Caller尽到某些义务，比如确保“如果number在数组a中存在，一定能找出来并返回它的位置，如果number在数组a中不存在，一定能返回-1”，这称为Postcondition。如果每个函数的文档都非常清楚地记录了Precondition、Maintenance和Postcondition是什么，那么每个函数都可以独立地编写和测试，整个系统就会易于维护。这种编程思想是由Eiffel语言的设计者Bertrand Meyer提出来的，称为Design by Contract（DbC）。

测试一个函数是否正确需要把Precondition、Maintenance和Postcondition这三方面都测试到，比如binarysearch这个函数，即使它写得非常正确，既维护了Invariant也保证了Postcondition，如果调用它的Caller没有保证Precondition，最后的结果也还是错的。我们编写两个测试用的Predicate函数，然后把相关的测试插入到binarysearch函数中：

#include <stdio.h>
#include <assert.h>

#define LEN 8
int a[LEN] = { 1, 3, 3, 3, 4, 5, 6, 7 };

int is_sorted()
{
	int i, sorted = 1;

	for (i = 1; i < LEN; i++)
		sorted = sorted && a[i-1] <= a[i];
	return sorted;
}

int mustbe(int start, int end, int number)
{
	int i;
	
	for (i = 0; i < LEN; i++) {
		if (i >= start && i <= end)
			continue;
		if (a[i] == number)
			return 0;
	}
	return 1;
}

int binarysearch(int number)
{
	int mid, start = 0, end = LEN - 1;

	assert(is_sorted()); /* Precondition */
	while (start <= end) {
		assert(mustbe(start, end, number)); /* Maintenance */
		mid = (start + end) / 2;
		if (a[mid] < number)
			start = mid + 1;
		else if (a[mid] > number)
			end = mid - 1;
		else
			return mid;
	}
	assert(mustbe(start, end, number)); /* Postcondition */
	return -1;
}

int main(void)
{
	printf("%d\n", binarysearch(3));
	return 0;
}

assert是头文件assert.h中的一个宏定义，执行到assert(is_sorted())这句时，如果is_sorted()返回值为真，则当什么事都没发生过，继续往下执行，如果is_sorted()返回值为假（例如把数组的排列顺序改一改），则报错退出程序：

main: main.c:33: binarysearch: Assertion `is_sorted()' failed.
Aborted

在代码中适当的地方使用断言（Assertion）可以有效地帮助我们测试程序。也许有人会问：binarysearch这个函数我们用两个测试函数is_sorted和mustbe来测试，那么这两个测试函数又用什么来测试呢？在实际工作中我们要测试的代码绝不会像binarysearch这么简单，而我们专为测试目的编写的测试函数往往都比较简单，比较容易保证正确性，也可以用一些简单的方法测试，这样就把测试复杂系统的问题转化为测试一些简单的测试函数的问题。

测试代码只在开发和调试时有用，如果已经发布（Release）的软件还要运行这些测试代码就会严重影响性能了，所以C语言规定，如果在包含assert.h之前定义一个NDEBUG宏（表示No Debug），就可以禁用assert.h中的assert宏定义，代码中的assert就不起任何作用了：

#define NDEBUG
#include <stdio.h>
#include <assert.h>
......

还有另一种办法，不必修改源文件，直接在编译时加上选项-DNDEBUG，相当于在文件开头定义NDEBUG宏。有关宏定义和预处理以后会更详细解释。