二分法查找（C語言）

二分法是一種高效的查找方法，其適用於已經排好序的數組

基本思路

從數組最中間的數開始查找判斷，若不是需要查找的數字，則比較大小，之後則在從中間分開的兩邊中的一邊從最中間開始查找判斷，以此類推

演算法描述

這裡以升序數組為例，降序數組類似

1. 記錄數組最中間數的下標，將其中的數與要查找的數進行比較
2. 若相等，停止查找，若大於要查找的數，則將數組下標上限換為較大半區的最小下標；若小於要查找的數，則將數組下標的下限換為較小半區的最大下標
3. 重覆第一步，直到數組下標不能調換，若查找到則停止查找，若未找到，則返回不存在的結果

代碼實現

這裡以升序數組為例，降序數組類似

# include<stdio.h>
int f(int, int [], int);
int main()
{
    int n;
    int arr[10]={1,2,3,4,5,6,7,8,9,10};
    scanf("%d", &n);//輸入要查找的數 
    int m=f(n, arr, 10-1);
    if(f(n, arr, 10-1)!=-1)
    printf("該數所在下標為：%d\n", m);
    else
    printf("該數不存在\n"); 
}
int f(int n, int a[], int h)
{
    int i, l, mid;
    l = 0;
    while(l<=h)//註意有等號,因為可能最後一次查找就只剩一個數,則這時上下限下標相等
    {
        mid=(l+h)/2;//計算中間下標
        if(a[mid]==n)//判斷是否為目標數
        return mid;
        else if(a[mid]<n)
        l=mid+1;//如果中間數小於目標數,則將數組下限改為較大半區的下限
        else 
        h=mid-1;//如果中間數大於目標數,則將數組上限改為較小半區的上限
    }
    return -1;//返回-1表示目標數不存在
}