C語言之折半查找(二分查找)-創(chuàng)新互聯(lián)

一、什么是折半查找?

創(chuàng)新互聯(lián)建站長期為近1000家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為樊城企業(yè)提供專業(yè)的成都做網(wǎng)站、網(wǎng)站制作，樊城網(wǎng)站改版等技術(shù)服務(wù)。擁有十多年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。

二分查找又稱折半查找，優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好；其缺點(diǎn)是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。
算法復(fù)雜度編輯
二分查找的基本思想是將n個(gè)元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x,算法中止；如果x<a[n/2],則只要在數(shù)組a的左半部分繼續(xù)搜索x,如果x>a[n/2],則只要在數(shù)組a的右半部搜索x.
時(shí)間復(fù)雜度無非就是while循環(huán)的次數(shù)！
總共有n個(gè)元素，
漸漸跟下去就是n,n/2,n/4,....n/2^k（接下來操作元素的剩余個(gè)數(shù)），其中k就是循環(huán)的次數(shù)
由于你n/2^k取整后>=1
即令n/2^k=1
可得k=log2n,（是以2為底，n的對數(shù)）
所以時(shí)間復(fù)雜度可以表示O()=O(logn)

二、折半查找原理

查找過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結(jié)束;如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。

三、C語言程序代碼

#include<stdio.h>
int binserch(int x,int m[],int n);
int main()
{
int a,jieguo;
int m[10]={1,2,3,4,5,6,7,8,9,10};
printf("請輸入要找的數(shù):");
scanf("%d",&a);
jieguo=binserch(a,m,10);
if(jieguo==-1)
printf("沒找到!\n");
else
printf("在m[%d]位置找到%d\n",jieguo,a);
return 0;
}
int binserch(int x,int m[],int n)//x是要找的數(shù),n為數(shù)據(jù)的長
{
int low,high,mid;
low=0;high=n-1;
while(low<=high)
{
    mid=(low+high)/2;
if(x<m[mid])
high=mid-1;
else if(x>m[mid])
    low=mid+1;
else
return mid;
}
return -1;
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

當(dāng)前題目：C語言之折半查找(二分查找)-創(chuàng)新互聯(lián)
轉(zhuǎn)載源于：http://muchs.cn/article2/cedoic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號、網(wǎng)站制作、外貿(mào)網(wǎng)站建設(shè)、品牌網(wǎng)站建設(shè)、云服務(wù)器、企業(yè)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)