順序查詢演算法和折半(二分法)查詢演算法,C語言查詢演算法詳解

2020-07-16 10:04:23
查詢是指在大量的資訊中尋找一個特定的資訊。在計算機中,查詢是非常重要的一個應用,比如“百度”。查詢演算法的好壞直接影響查詢的速度。

常用的查詢演算法主要有順序查詢折半(二分法)查詢
  • 順序查詢是指從陣列的一端開始逐個進行比較,直到找到該資料為止。
  • 折半查詢是指在已經排好序的一組資料中快速查詢資料。

現實程式設計中,資料一般都是有序的。即使剛開始是無序的,但儲存到資料庫中時都是先將它們排好序然後再放進去,這樣在實際應用中才能更方便。

順序查詢

查詢陣列 a 中第一次出現數位 m 的下標並輸出該下標,如果沒有則輸出“sorry”,實現程式碼如下:
# 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;
}
輸出結果是:
請輸入一個數位:7
下標 = 21
請輸入一個數位:58
sorry

折半查詢

折半查詢是很有意思的,它的演算法複雜度非常低,但它要求資料必須是已經排好序的。比如陣列 a 中:

13  45  78  90  127  189  243  355

現在看看怎麼用折半演算法在其中查詢 243。
1) 先定義一個變數 key 用於存放要查詢的 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,找到了。

下面再來怎麼查詢 78:
1) key=78,mid=(low+high)/2=(0+7)/2=3。

2) 此時 a[3]=90,而 key<90,說明 78 在 90 的左邊,則往前查詢:

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,就找到了。

若所查詢的在資料序列中沒有呢?比如查詢 123:
1) key=123,mid=(low+high)/2=(0+7)/2=3。

2) 此時 a[3]=90,而 key>90,說明 123 在 90 的左邊,則往後查詢:

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;
}
輸出結果是:
請輸入您想查詢的數:78
下標 = 2
請輸入您想查詢的數:123
sorry, data is not found

折半查詢在每次查詢時都排除了一半資料,所以它的效率是非常高的。順序查詢的平均查詢長度為 n+1/2,而折半查詢的平均查詢長度為 log2(n+1)-1。可見使用折半查詢時,資料數量越多查詢效率就越高。

但是,折半查詢只適合陣列,不適合連結串列。連結串列中也可以用折半查詢,但是不僅不會提高效率,反而還會降低效率。因為陣列可以通過下標直接找到 low、mid 和 high 對應的元素,而連結串列是通過指標連線起來的不連續的鏈,所以若要查詢 low、mid 和 high 對應的元素,每次都要從第一個結點出發一個一個往後找。所以一般不在連結串列內使用折半查詢。