// Fig. 6.19: fig06_19.c // Binary search of a sorted array.
#include <stdio.h>
#define SIZE 15
// function prototypes
size_t binarySearch(const int b[], int searchkey, size_t low, size_t high);
void printHeader(void);
void printRow(const int b[], size_t low, size_t mid, size_t high);
// function main begins program execution
int main(void) {
int a[SIZE]; // create array a
// create data
for (size_t i = 0; i < SIZE; ++i) {
a[i] = 2 * i + 1;
}
printf("%s", "Enter a number between 0 and 28: ");
int key; // value to locate in array a
scanf("%d", &key);
printHeader();
// search for key in array a
size_t result = binarySearch(a, key, 0, SIZE - 1);
// display results
if (result != -1) {
printf("\\n%d found at index %zu\\n", key, result);
} else {
printf("\\n%d not found\\n", key);
}
return 0;
}
// function to perform binary search of an array
size_t binarySearch(const int b[], int searchkey, size_t low, size_t high) {
// loop until low index is greater than high index
while (low <= high) {
// determine middle element of subarray being searched
size_t middle = (low + high) / 2;
// display subarray used in this loop iteration
printRow(b, low, middle, high);
// if searchkey matched middle element, return middle
if (searchkey == b[middle]) {
return middle;
}
// if searchkey is less than middle element, set new high
else if (searchkey < b[middle]) {
high = middle - 1; // search low end of array
}
// if searchkey is greater than middle element, set new low
else {
low = middle + 1; // search high end of array
}
}
return -1; // searchkey not found
}
// Print a header for the output
void printHeader(void) {
puts("\\nIndices:");
// output column head
for (unsigned int i = 0; i < SIZE; ++i) {
printf("%3u ", i);
}
puts(""); // start a new line of output
// output line of characters
for (unsigned int i = 1; i <= SIZE * 4; ++i) {
printf("%s", "-");
}
puts(""); // start a new line of output
}
// Print one row of output showing the current
// part of the array being processed.
void printRow(const int b[], size_t low, size_t mid, size_t high) {
// loop through the entire array
for (size_t i = 0; i < SIZE; ++i) {
// display spaces if outside the current subarray range
if (i < low || i > high) {
printf("%4s", "");
} else if (i == mid) { // display middle element
printf("%3d*", b[i]); // mark the middle value
} else { // display other elements in the subarray
printf("%3d ", b[i]);
}
}
puts(""); // start a new line of output
}
6.10 搜尋陣列 將來會常碰到存放在陣列裡的大量資料，有時候可能需要知道陣列中是否有㇐個符合某個關鍵值 (key value) 的數值。找出陣列中某個元素的過程稱為搜尋 (searching)。 本節介紹兩種搜尋的技術：最簡單的線性搜尋(linear search)技巧和較有效率(也較複雜)的二元搜尋(binary search)技巧。6.10.1 使用線性搜尋來搜尋陣列 線性搜尋(圖 6.18)用搜尋關鍵值(search key)來比較陣列中的每個元素。由於陣列中並沒有任何特別的順序，所以有可能在第㇐次比較就找到，也有可能要到最後㇐個元素オ能找到。平均來說，程式需要㇐半的陣列元素來與搜尋關鍵値比較。
6.10.2 使用二元搜尋來搜尋陣列 對於小型陣列或未排序過的陣列而言，線性搜尋可以表現得很好。但是將線性搜尋用在大型陣列上，就很没有效率了。如果陣列已排序過了，則可以用速度很快的二元搜尋法。 二元搜尋演算法在每次比較之後，就可以將已排序陣列中㇐半的元素刪去不考應。此演算法先找出陣列的中間元素，將之與搜尋關鍵值做比較。如果相等的話，表示已找到搜尋關鍵值，就將此元素的陣列索引傳回。如果不相等，此時問題便簡化成只需搜尋陣列的某㇐半。
6.10.2 使用二元搜尋來搜尋陣列 如果搜尋關鍵值小於陣列的中間元素，演算法就搜尋陣列的前半部；否則就會搜尋陣列的後半部。 假如在指定的子陣列(原始陣列的㇐部分)當中，搜尋關鍵值並非中間元素，演算法就會重複搜尋原始陣列的四分之㇐。搜尋的動作會㇐直持續到搜尋關鍵值等於子陣列的中間元素為止，或是子陣列只包含㇐個與搜尋關鍵值不相等的元素為止(也就是沒有找到搜尋關鍵值)。
6.10.2 使用二元搜尋來搜尋陣列 在最壞的情形之下，使用二元搜尋來搜尋 1023 個元素的已排序陣列只需10次比較。重複將1024除以2將會得到512、256、128、64、32、16、8、4、2、1等數值。即 1024 (210)，只要除以2十次，便可得到值1。 除以2的動作相當於二元搜尋演算法的比較動作，㇐個具有1,048,576(220)個元素的已排序陣列，最多只需要進行20次的比較，就能找到搜尋關鍵值。 而㇐個具有十億個元素的已排序陣列，最多也只需要30次此較便能找到搜尋關鍵值。這比起線性搜尋㇐個已排序的陣列，有了大幅的效能政進，線性搜尋找到搜尋關鍵值所需要的比較次數，平均為陣列元素個數的㇐半。 對㇐個具有十億個元素的陣列來說，平均要比較 5 億次(線性搜尋)，與最多比較30次相比，其差別是很大的。任何㇐個陣列的最大比較次數，可以由大於此陣列元素個數的第㇐個2的次方數來加以決定。
6.10.2 使用二元搜尋來搜尋陣列 圖6.19的程式為binarySearch函式的循環結構版本(#40-68)。此函式接收四個引數：被搜尋的整數陣列b、㇐個整數searchKey、陣列的low索引，和陣列的high索引(這些引數定義了陣列要搜尋的部分)。如果搜尋關鍵值不等於子陣列的中間元素，則low索引或high索引將會受到更改。 所以它能夠繼續搜尋較小範圍的子陣列，如果搜尋關鍵值小於中間元素，high索引將設定為middle-1，接下來程式會繼續搜尋low到middle-1的元素。 如果搜尋關鍵值大 於中間元素，則low索引將會 設定 為middle+1，接下來程式會繼續搜尋middle+1至high之間的元素。
6.10.2 使用二元搜尋來搜尋陣列 這個程式使用15個元素的陣列，第㇐個大於15的2的次方數是16 (24)，因此最多只需要 4 次便能找到關鍵值。 這個程式使用printHeader函式(#71-88)來輸出陣列索引，並且使用printRow函式(#92-110)在二元搜尋的過程中輸出每個子陣列，每個子陣列的中間元素都會標上星號(*)，來表示此元素將與搜尋關鍵值進行比較。
