C語言折半查找法的超詳細(xì)講解
折半查找法僅適用于對已有順序的數(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)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語言中isdigit()函數(shù)和isxdigit()函數(shù)的用法
這篇文章主要介紹了C語言中isdigit()函數(shù)和isxdigit()函數(shù)的用法,用來判斷字符師傅為阿拉伯?dāng)?shù)字和16進(jìn)制數(shù)字,需要的朋友可以參考下2015-08-08C++ 項目引入lib和dll的區(qū)別與使用實戰(zhàn)
靜態(tài)鏈接庫與動態(tài)鏈接庫都是共享代碼的方式,本文主要介紹了C++項目引入lib和dll的區(qū)別與使用實戰(zhàn),具有一定的參考價值,感興趣的可以了解一下2024-02-02淺談C語言共用體和與結(jié)構(gòu)體的區(qū)別
下面小編就為大家?guī)硪黄獪\談C語言共用體和與結(jié)構(gòu)體的區(qū)別。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-02-02