折半查找算法

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

#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;
}

測試一個函數是否正確需要把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;