一、什么是折半查找?

創新互聯建站長期為近1000家客戶提供的網站建設服務，團隊從業經驗10年，關注不同地域、不同群體，并針對不同對象提供差異化的產品和服務；打造開放共贏平臺，與合作伙伴共同營造健康的互聯網生態環境。為樊城企業提供專業的成都做網站、網站制作，樊城網站改版等技術服務。擁有十多年豐富建站經驗和眾多成功案例,為您定制開發。

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

二、折半查找原理

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

三、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("請輸入要找的數:");
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是要找的數,n為數據的長
{
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;
}

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

當前題目：C語言之折半查找(二分查找)-創新互聯
轉載源于：http://vcdvsql.cn/article2/cedoic.html

成都網站建設公司_創新互聯，為您提供微信公眾號、網站制作、外貿網站建設、品牌網站建設、云服務器、企業建站

廣告

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