C語言折半查找法的超詳細(xì)講解

更新時間：2022年06月17日 09:57:23 作者：一個愛好編程的大學(xué)生i

折半查找法也叫做?分查找,顧名思義就是把數(shù)據(jù)分成兩半,再判斷所查找的key在哪?半中,再重復(fù)上述步驟知道找到?標(biāo)key,下面這篇文章主要給大家介紹了關(guān)于C語言折半查找法的相關(guān)資料,需要的朋友可以參考下

折半查找法僅適用于對已有順序的數(shù)組、數(shù)據(jù)進(jìn)行操作?。。。◤男〉酱螅┳晕铱偨Y(jié)：折半查找法就是相當(dāng)于（通過改變low或high的大?。┌阎虚g位置指到了key那個數(shù)那里，所以mid應(yīng)該處于循環(huán)里面，即mid=（high+low）/2。注意：low，mid，high都要與下標(biāo)綁定，也就是說它們就是下標(biāo)。且循環(huán)條件是：high>=low.

同時注意：⑴若原來數(shù)組是由小到大排列的則：

? ? ? mid=(high+low)/2;
? ? ? ? ? ? if(key<a[mid])//說明要找的值在左邊
? ? ? ? ? ? high=mid-1;
? ? ? ? ? ? else if(key>a[mid])//說明要找的值在mid右邊
? ? ? ? ? ? low=mid+1;//最小值的位置往右進(jìn)一位

㈡若原來數(shù)組是由大到小排列的則：

mid=(high+low)/2;
? ? ? ? ? ? if(key>a[mid])//注意是由大到小排列 ，所以此時key在a【mid】 左邊，故high=mid-1 ；
? ? ? ? ? ? high=mid-1;
? ? ? ? ? ? else if(key<a[mid])//注意是由大到小排列，所以此時key在a【mid】右邊，故low=mid+1；
? ? ? ? ? ? low=mid+1;

當(dāng)然在下面這個代碼中，也可以用選擇排序法和冒泡法來對任意數(shù)組進(jìn)行排序，然后在應(yīng)用此函數(shù)，保證折半查找法的前提是排好序了。

#include<stdio.h>
 void zb(int key,int a[],int n)//key表示要找的數(shù)，a表示數(shù)組，n表示數(shù)組元素個數(shù) 
 {
     int i,high,low,mid;
     int count1=0,count=0;
     low=0;
     high=n-1;
     while(high>=low)//保證右下標(biāo)不小于左下標(biāo) 
     {    
        count++;
        mid=(high+low)/2;//總的來說變得是中間位置相當(dāng)于把中間位置移到了key那個數(shù)那里，所以mid應(yīng)該處于循環(huán)里面 
         if(key<a[mid])//說明key在a【mid】的左半邊 ,那么最右邊的high下標(biāo)就可以在下標(biāo)mid基礎(chǔ)上往左進(jìn)一個單位了
        high=mid-1;
         else if(key>a[mid])//說明key在a【mid】的右半邊 ,那么最左邊的low下標(biāo)就可以在下標(biāo)mid基礎(chǔ)上往右進(jìn)一個單位了 
         low=mid+1;
        if(key==a[mid])
        {
            printf("元素找到了！??！\n一共查找了%d次\n它處于a[%d]位置上\na[%d]=%d\n",count,mid,mid,key);
            count1++;
            break;
        }
    }
     if(count1==0)
     printf("元素不存在！??！\n");
 }
 int main ()
 {
     int key,n,a[100];
     int i;
     void zb(int key,int a[],int n);//聲明定義函數(shù) 
     printf("請輸入數(shù)組元素個數(shù)：\n");
     scanf("%d",&n);
     printf("請輸入（從小到大）所有數(shù)組元素：\n");
     for(i=0;i<n;i++)
     {
         scanf("%d",&a[i]);
     }
     printf("請輸入要查找的數(shù)：\n");
     scanf("%d",&key);
     zb(key,a,n);
     printf("\n");
     return 0;
 }

總結(jié)

到此這篇關(guān)于C語言折半查找法的文章就介紹到這了,更多相關(guān)C語言折半查找法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: