如果不是從一組隨機的序列裡查找，而是從一組排好序的序列裡找出某個元素的位置，則可以有更快的算法：

#include <stdio.h>

#define LEN 8
int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };

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(5));
	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, 2, 2, 2, 5, 6, 8, 9 };

int is_sorted(void)
{
	int i;
	for (i = 1; i < LEN; i++)
		if (a[i-1] > a[i])
			return 0;
	return 1;
}

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

int contains(int n)
{
	int i;
	for (i = 0; i < LEN; i++)
		if (a[i] == n)
			return 1;
	return 0;
}

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 {
			assert(mid >= start && mid <= end
			       && a[mid] == number) /* Postcondition 1 */
			return mid;
		}
	}
	assert(!contains(number)); /* Postcondition 2 */
	return -1;
}

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

assert是標頭檔assert.h中的一個宏定義，執行到assert(is_sorted())這句時，如果is_sorted()返回值為真，則當什麼事都沒發生過，繼續往下執行，如果is_sorted()返回值為假（例如把數組的排列順序改一改），則報錯退出程序：

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

在代碼中適當的地方使用斷言（Assertion）可以有效地幫助我們測試程序。也許有人會問：我們用幾個測試函數來測試binarysearch，那麼這幾個測試函數又用什麼來測試呢？在實際工作中我們要測試的代碼絶不會像binarysearch這麼簡單，而我們編寫的測試函數往往都很簡單，比較容易保證正確性，也就是用簡單的、不容易出錯的代碼去測試複雜的、容易出錯的代碼。

測試代碼只在開發和調試時有用，如果正式發佈（Release）的軟件也要運行這些測試代碼就會嚴重影響性能了，如果在包含assert.h之前定義一個NDEBUG宏（表示No Debug），就可以禁用assert.h中的assert宏定義，這樣代碼中的所有assert測試都不起作用了：

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

注意NDEBUG和我們以前使用的宏定義有點不同，例如#define N 20將N定義為20，在預處理時把代碼中所有的標識符N替換成20，而#define NDEBUG把NDEBUG定義為空，在預處理時把代碼中所有的標識符NDEBUG替換成空。這樣的宏定義主要是為了用#ifdef等預處理指示測試它定義過沒有，而不是為了做替換，所以定義成什麼值都無所謂，一般定義成空就足夠了。

還有另一種辦法，不必修改源檔案，在編譯命令行加上選項-DNDEBUG就相當於在源檔案開頭定義了NDEBUG宏。宏定義和預處理到第 21 章 預處理再詳細解釋，在第 4 節 “其它預處理特性”將給出assert.h一種實現。

double product = 1;
for (i = 0; i < n; i++)
	product *= x;