C語言二分查找（折半查找）算法及代碼

二分査找也稱折半査找，其優點是查找速度快，缺點是要求所要査找的數據必須是有序序列。該算法的基本思想是將所要査找的序列的中間位置的數據與所要査找的元素進行比較，如果相等，則表示査找成功，否則將以該位置為基准將所要査找的序列分為左右兩部分。接下來根據所要査找序列的升降序規律及中間元素與所查找元素的大小關系，來選擇所要査找元素可能存在的那部分序列，對其采用同樣的方法進行査找，直至能夠確定所要查找的元素是否存在，具體的使用方法可通過下面的代碼具體了解。

#include <stdio.h>

binarySearch(int a[], int n, int key){
    int low = 0;
    int high = n - 1;
    while(low<= high){
        int mid = (low + high)/2;
        int midVal = a[mid];
        if(midVal<key)
            low = mid + 1;
        else if(midVal>key)
            high = mid - 1;
        else
            return mid;
    }
    return -1;
}

int main(){
    int i, val, ret;
    int a[8]={-32, 12, 16, 24, 36, 45, 59, 98};
    for(i=0; i<8; i++)
        printf("%d\t", a[i]);

    printf("\n請輸人所要查找的元素：");
    scanf("%d",&val);

    ret = binarySearch(a,8,val);

    if(-1 == ret)
        printf("查找失敗 \n");
    else
        printf ("查找成功 \n");

    return 0;
}

運行結果：

-32    12    16    24    36    45    59    98
請輸入所要查找的元素：12
查找成功

在上面的代碼中，我們成功地通過二分査找算法實現了查找功能，其實現過程如下圖所示。


二分査找算法的査找過程
在如上圖所示的查找過程中，先將序列中間位置的元素與所要査找的元素進行比較，發現要査找的元素位干該位置的左部分序列中。接下來將mid的左邊一個元素作為 high，繼續進行二分査找，這時mid所對應的中間元素剛好是所要査找的元素，査找結束，返回査找元素所對應的下標。在main函數中通過返回值來判斷査找是否成功，如果査找成功.就打印輸出“査找成功”的信息，否則輸出“査找失畋”的信息。