C語言折半查詢法介紹及使用範例

2022-08-11 18:01:37

1. 折半查詢介紹

1.1 定義

折半查詢也稱二分查詢，是一種在有序陣列中查詢某一特定元素的搜尋演演算法，每一次查詢，搜尋範圍均縮小一半，效率較高。如果陣列是亂序狀態，則應排序，再進行查詢。

1.2 基本原理

搜尋過程從陣列的中間元素開始，如果中間元素正好是要查詢的元素，則搜尋過程結束；如果某一特定元素大於或者小於中間元素，則在陣列大於或小於中間元素的那一半中查詢，而且跟開始一樣從中間元素開始比較。如果在某一步驟陣列為空，則代表找不到。這種搜尋演演算法每一次比較都使搜尋範圍縮小一半。

1.3 時間複雜度與空間複雜度

總共有n個元素，每次查詢的區間大小就是n，n/2，n/4，…，n/ 2 k 2^k 2k，一直到1，其中k就是迴圈的次數。

由於n/ 2 k 2 ^ k 2k取整後>=1，即令n/ 2 k 2^k 2k=1，可得k=log2n,（是以2為底，n的對數），所以時間複雜度可以表示O()=O(logn)。

二分查詢只需要額外儲存三個變數：最大值，最小值和中點，空間複雜度為常數 O(1)。

1.4 優缺點

優點：比較次數少，查詢速度快，平均效能好。

缺點：要求待查表為有序表，且插入刪除困難。

2. 程式碼實現

2.1 程式碼設計

輸入需要查詢的元素，我們輸入的是38；left是有序陣列最左端0，是最小值，right是有序陣列最右端10，是最大值，mid為陣列1/2位置，即array[5]；
38比array[5] = 19大，因此left等於原mid+1，即array[6] = 26，right不變；新mid為(left+right)/2 = （6+10）/2 = 8；
38比array[8] = 36大，因此left等於上一次mid+1，即array[9] = 38，right不變；新mid為(left+right)/2 = （9+10）/2 = 9；
38等於array[9]，mid與left重合，查詢成功，返回陣列下標9.

2.2 程式碼實現

#include <stdio.h>
#include <string.h>
int binarySearch(int array[],int len,int target){
    int left = 0;
    int right = len - 1;
    while(left <= right){
        int mid = (right + left) / 2;
        if(array[mid] == target){
            return mid;
        } else if(array[mid] < target){
            left = mid + 1;
        } else if(array[mid] > target){
            right = mid - 1;
        }
    }
    return -1;
}
int main(void)
{
    int array[]={2,3,4,5,15,19,26,27,36,38,45};
    int key = 0,ret;
    printf("請輸入需要查詢的數位:");
    scanf("%d",&key);
    ret = binarySearch(array,sizeof(array)/sizeof(int),key);
    if(ret < 0)
        printf("查詢失敗n");
    else
        printf("該數位為陣列第%d個元素n",ret+1);
    return 0;
}

執行結果：

請輸入需要查詢的數位:38

該數位為陣列第10個元素

到此這篇關於C語言折半查詢法介紹及使用範例的文章就介紹到這了,更多相關C語言折半查詢內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！