[科普中國]-折半查找法

概述

折半查找法是效率較高的一種查找方法。假設(shè)有已經(jīng)按照從小到大的順序排列好的五個整數(shù)a0~a4，要查找的數(shù)是X，其基本思想是： 設(shè)查找數(shù)據(jù)的范圍下限為l=0，上限為h=4，求中點m=（l+h）/2，用X與中點元素am比較，若X等于am，即找到，停止查找；否則，若X大于am，替換下限l=m+1，到下半段繼續(xù)查找；若X小于am，換上限h=m-1，到上半段繼續(xù)查找；如此重復(fù)前面的過程直到找到或者l>h為止。如果l>h，說明沒有此數(shù)，打印找不到信息，程序結(jié)束。2

該方法是查找的范圍不斷縮小一半，所以查找效率較高。2

加倍折半法 的關(guān)鍵是如何“加倍”、“折半”。那么“加倍”、“折半”的方法又是什么呢？傳統(tǒng)的“加倍”的方法，是將線段延長一倍；傳統(tǒng)的“折半”的方法，是取線段的中點。豈不知，“三角形中位線定理”、“直角三角形斜邊上的中線等于斜邊的一半”、“等腰三角形的三線合一性質(zhì)”、“平行線等分線段定理”……均有“加倍、折半”的功用。也就是說“加倍”“折半”的方法是眾多的、豐富的。而這些的方法基本上都是來自上述的一些重要的定理。

例1 已知：△ABC中，AB=AC,延長AB到D，使DB=AB，E是AB的中點。求證：CD=2CE

思路一：延長CE到F1，使EF1=CE，即用

延長的方法將CE擴大一倍為CF1，證CF1=CD

思路二：取CD的中點，即用“取中點”的方法將CD縮小一半為CF2，證CF2=CE。

以上為“傳統(tǒng)”的加倍折半法，引申后則有：

思路三：抓住E為AB中點這一特點，作△ABF3，使CE為該三角形的中位線（過A作AF3∥CE，交BC的延長線于F3），即用三角形中位線定理將CE擴大一倍為AF3，證AF3=CD

思路四：抓住B為AD中點這一特點，作△ADC以CD邊為底邊的中位線（過B作BF4∥CD，交AC于F4），即：用三角形中位線定理將CD縮小一半為BF4，證BF4=CE

引申對三角形加倍折半法“用途”的引申

傳統(tǒng)的加倍折半法主要應(yīng)用于線段（或角）倍半關(guān)系的證明。隨著“方法”的引申，其功能也隨之得到了增強。特別是完全領(lǐng)會了加倍折半法的基本思想后，許多疑難問題就會迎刃而解。它的用途遠遠超出了原先的范圍，幾乎適用于所有含“2”的類型題。下面，分“結(jié)論中含有2”和“題設(shè)中含有2”兩中情況作簡單的介紹。

1、加倍折半法來解“結(jié)論中含有2”的類型題，實際上就是“分析法”的一種具體應(yīng)用?！凹颖墩郯敕ā痹诖似鸬淖饔?，也可稱之為“解題技巧”。例1屬于該種類型的“傳統(tǒng)”例題，下面舉幾個引申后的例子。

例2 已知：△ABC中，D是BC上的中點，F(xiàn)是AD上的任意一點，延長CF交AB于E。求證：AF：DF=2AE：BE

思路：本題的難點是如何除去比例式中的“2”

方法一：將AE或DF“加倍”，由于D是BC的中點，

過點B作BG∥DF，交CE的延長線于G，則用三角形中位線定理將DF“擴大一倍”為BG。這樣，原題就有效的轉(zhuǎn)化為證明AF：BG=AE：BE。

方法二：是將AF或BE“折半”，由于D是BC的中點，過點D作DH∥AB，交CE于GH，則用三角形中位線的定理將BE“縮小一半”為DH。這樣，原題就有效的轉(zhuǎn)化為證明AF：DF=AE：DH。

2、用加倍折半法來解“題設(shè)中含有2”的類型題，實際上就是“綜合法”的一種具體的應(yīng)用。“加倍折半法”在此起的作用，可稱之為“解題經(jīng)驗”。

例3 已知：△ABC中，AD是高線，∠ABC=2∠ACB。求證：CD=AB+BD

思路：該題屬于“截長補短法”的習題，

但由于已知條件中有角的倍半關(guān)系，因

而用“加倍折半法”的思路也可以解決。

思路一：延長DB到E1，使BE1=BA（造等腰三角形將∠ABC“折半“為E1），則∠E1=∠C，AE1=AC，CD=DE1，故CD=AB+BD

思路二：作∠CAE2，使∠CAE2=∠C（造等腰三角形將∠C“加倍”為∠AE2B），則∠AE2B=∠ABC，AE2=E2C=AB，BD=DE2，故CD=AB+BD。

優(yōu)缺點Bentley在他的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內(nèi)寫出完全正確的二分搜索算法。問題的關(guān)鍵在于準確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數(shù)的各種情況，其實整理后可以發(fā)現(xiàn)它的具體算法是很直觀的。

折半查找法的優(yōu)點是比較次數(shù)少，查找速度快，平均性能好；

其缺點是要求待查表為有序表，且插入刪除困難。

因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。

算法步驟描述① 首先確定整個查找區(qū)間的中間位置 mid = （ left + right ）/2 。

② 用待查關(guān)鍵字值與中間位置的關(guān)鍵字值進行比較； 若相等，則查找成功 若大于，則在后（右）半個區(qū)域繼續(xù)進行折半查找 若小于，則在前（左）半個區(qū)域繼續(xù)進行折半查找。

③ 對確定的縮小區(qū)域再按折半公式，重復(fù)上述步驟。最后，得到結(jié)果：要么查找成功， 要么查找失敗。折半查找的存儲結(jié)構(gòu)采用一維數(shù)組存放3。

基本算法實現(xiàn)函數(shù)bin_search(int A[],int n,int key){

int low,high,mid;

low = 0;

high = n-1;

while(lowa[mid]) min=mid;

else if (n