利用數(shù)組進行數(shù)據(jù)查找_折半查找法_C語言程序.doc

《利用數(shù)組進行數(shù)據(jù)查找_折半查找法_C語言程序.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、適應(yīng)情況：在一批有序數(shù)據(jù)中查找某數(shù)基本思想：選定這批數(shù)中居中間位置的一個數(shù)與所查數(shù)比較，看是否為所找之數(shù)，若不是，利用數(shù)據(jù)的有序性，可以決定所找的數(shù)是在選定數(shù)之前還是在之后，從而很快可以將查找范圍縮小一半。以同樣的方法在選定的區(qū)域中進行查找，每次都會將查找范圍縮小一半，從而較快地找到目的數(shù)例7.10假設(shè)在數(shù)組a中的數(shù)據(jù)是按由小到大順序排列的：-120616235680100110115，從鍵盤上輸入一個數(shù)，判定該數(shù)是否在數(shù)組中，若在，輸出所在序號；若不在，輸出相應(yīng)信息。查找過程如下：第一步：設(shè)low、mid和high三個變量

2、，分別指示數(shù)列中的起始元素、中間元素與最后一個元素位置,其初始值為low=0,high=9,mid=4，判斷mid指示的數(shù)是否為所求，mid指示的數(shù)是23，不是要找的80，須繼續(xù)進行查找。[-120616235680100110115]↑low↑mid↑high第二步：確定新的查找區(qū)間。因為80大于23，所以查找范圍可以縮小為23后面的數(shù)，新的查找區(qū)間為[5680100110115]，low,mid,high分別指向新區(qū)間的開始、中間與最后一個數(shù)。實際上high不變，將low（low=mid+1）指向56,mid（mid=(

3、low+high)/2）指向100,還不是要找的80，仍須繼續(xù)查找。-12061623[5680100110115]↑low↑mid↑high?第三步：上一步中，所找數(shù)80比mid指示的100小，可知新的查找區(qū)間為[5680]，low不變，mid與high的值作相應(yīng)修改。mid指示的數(shù)為56，還要繼續(xù)查找。-12061623[5680]100110115↑low↑high↑mid第四步：根據(jù)上一步的結(jié)果，80大于mid指示的數(shù)56，可確定新的查找區(qū)間為[80]，此時，low與high都指向80，mid亦指向80，即找到了80

4、，到此為止，查找過程完成。-1206162356[80]100110115↑low↑mid↑high若在查找過程中，出現(xiàn)low>high的情況，則說明，序列中沒有該數(shù)，亦結(jié)束查找過程。?程序為：#defineM10#includemain(){staticinta[M]={-12,0,6,16,23,56,80,100,110,115};intn,low,mid,high,found;low=0;high=M-1;found=0;printf("Inputanumbertobesearched:");sca

5、nf("%d",&n);while(low<=high){mid=(low+high)/2;if(n==a[mid]){found=1;break;}/*找到，結(jié)束循環(huán)*/elseif(n>a[mid])low=mid+1;elsehigh=mid-1;}if(found==1)printf("Theindexof%dis%d",n,mid);elseprintf("Thereisnot%d",n);}輸入：80↙輸出：Theindexof80is6