# include <stdio.h> int main(void) { int a[] = {1,5,66,8,55,9,1,32,5,65,4,8,5,15,64,156,1564,15,1,8,9,7,215, 16,45,5,6,164,15,236,2,5,55,6,4,1,59,23,4,5,314,56,15,3,54, 1,54,54,2,4,4,5,15,698,486,56,26,98,78,456,1894,564,26,56,5}; int n; //存放陣列a中元素的個數 int m; //查詢的數位 int i; //迴圈變數 n = sizeof(a) / sizeof(int); //求出陣列中所有元素的個數 printf("請輸入一個數位:"); scanf("%d", &m); for (i=0; i<n; ++i) { if (a[i] == m) { printf("下標 = %dn", i); break; } } if (i == n) { printf("sorryn"); } return 0; }輸出結果是:
13 45 78 90 127 189 243 355
現在看看怎麼用折半演算法在其中查詢 243。key = 243
2) 定義變數 low、mid和high 分別儲存陣列的最小下標、中間下標和最大下標。並有:mid = (low+high)/2 = (0+7)/2 = 3
3) 此時 a[3]=90,而 key>90,說明 243 在 90 的右邊,則往後查詢:low = mid + 1 = 4
4) 然後重新更新 mid:mid = (4+7)/2 = 5
5) 此時 a[5]=189,而 key>189,說明 243 在 189 的右邊,繼續往後查詢:low = mid+1 = 6
6) 然後重新更新 mid:mid = (6+7)/2 = 6
7) 此時 a[6]=key=243,找到了。high = mid-1 = 2
3) 然後重新更新 mid:mid = (0+2)/2 = 1
4) 此時 a[1]=45,而 key>45,說明 78 在 45 的右邊,則往後查詢:low = 1+1 = 2
5) 然後重新更新 mid:mid = (2+2)/2 = 2
6) 此時 a[2]=key=78,就找到了。low = mid+1 = 4
3) 然後重新更新 mid:mid = (4+7)/2 = 5
4) 此時 a[5]=189,而 key<189,說明 123 在 189 的左邊,則往前查詢:high=mid-1=4。
5) 此時 low==high,如果該數仍不是要找的數的話,說明該序列中就沒有該數了。# include <stdio.h> int main(void) { int a[] = {13, 45, 78, 90, 127, 189, 243, 355}; int key; //存放要查詢的數 int low = 0; int high = sizeof(a)/sizeof(a[0]) - 1; int mid; int flag = 0; //標誌位, 用於判斷是否存在要找的數 printf("請輸入您想查詢的數:"); scanf("%d", &key); while ((low <= high)) { mid = (low + high) / 2; if (key < a[mid]) { high = mid - 1; } else if (a[mid] < key) { low = mid +1; } else { printf("下標 = %dn", mid); flag = 1; break; } } if (0 == flag) { printf("sorry, data is not foundn"); } return 0; }輸出結果是:
n+1/2
,而折半查詢的平均查詢長度為 log2(n+1)-1。可見使用折半查詢時,資料數量越多查詢效率就越高。