C語言二分查詢演算法，折半查詢演算法

本範例採用二分查詢法查詢特定關鍵字的元素。要求使用者輸入陣列長度，也就是有序表的資料長度，並輸入陣列元素和査找的關鍵字。程式輸出查詢成功與否，以及成功時關鍵字在陣列中的位置。例如，在有序表 11、13、18、 28、39、56、69、89、98、122 中査找關鍵字為 89 的元素。

實現過程：

(1) 自定義函數 binary_search()，實現二分査找。

(2) main() 函數作為程式的入口函數。程式程式碼如下：

#include <stdio.h>
int binary_search(int key,int a[],int n) //自定義函數binary_search()
{
    int low,high,mid,count=0,count1=0;
    low=0;
    high=n-1;
    while(low<high)    //査找範圍不為0時執行迴圈體語句
    {
        count++;    //count記錄査找次數
        mid=(low+high)/2;    //求中間位置
        if(key<a[mid])    //key小於中間值時
            high=mid-1;    //確定左子表範圍
        else if(key>a[mid])    //key 大於中間值時
            low=mid+1;    //確定右子表範圍
        else if(key==a[mid])    //當key等於中間值時，證明查詢成功
        {
            printf("查詢成功!n 查詢 %d 次!a[%d]=%d",count,mid,key);    //輸出査找次數及所査找元素在陣列中的位置
            count1++;    //count1記錄查詢成功次數
            break;
        }
    }
    if(count1==0)    //判斷是否查詢失敗
        printf("查詢失敗!");    //査找失敗輸出no found
    return 0;
}

int main()
{
    int i,key,a[100],n;
    printf("請輸入陣列的長度：n");
    scanf("%d",&n);    //輸入陣列元素個數
    printf("請輸入陣列元素：n");
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);    //輸入有序數列到陣列a中
    printf("請輸入你想查詢的元素：n");
    scanf("%d",&key);    //輸入要^找的關鍵字
    binary_search(key,a,n);    //呼叫自定義函數
    printf("n");
    return 0;
}

執行結果：

請輸入陣列的長度：
10
請輸入陣列元素：
11 13 18 28 39 56 69 89 98 122
請輸入你想查詢的元素：
89
查詢成功!
查詢 2 次!a[7]=89

技術要點：

二分査找就是折半查詢，其基本思想是：首先選取表中間位置的記錄，將其關鍵字與給定關鍵字 key 進行比較，若相等，則査找成功；若 key 值比該關鍵字值大，則要找的元素一定在右子表中，則繼續對右子表進行折半查詢：若 key 值比該關鍵宇值小，則要找的元素一定在左子表中，繼續對左子表進行折半査找。如此遞推，直到査找成功或査找失敗（或査找範圍為 0）。