[科普中國(guó)]-二分搜索法

簡(jiǎn)介

在計(jì)算機(jī)科學(xué)中，二分搜索（英語(yǔ)：binary search），也稱(chēng)折半搜索（英語(yǔ)：half-interval search）、對(duì)數(shù)搜索（英語(yǔ)：logarithmic search），是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜索過(guò)程從數(shù)組的中間元素開(kāi)始，如果中間元素正好是要查找的元素，則搜索過(guò)程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開(kāi)始一樣從中間元素開(kāi)始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。1

如果xa[n/2]，則我們只要在數(shù)組a的右半部繼續(xù)搜索x。二分搜索法的應(yīng)用極其廣泛，而且它的思想易于理解，但是要寫(xiě)一個(gè)正確的二分搜索算法也不是一件簡(jiǎn)單的事。第一個(gè)二分搜索算法早在1946年就出現(xiàn)了，但是第一個(gè)完全正確的二分搜索算法直到1962年才出現(xiàn)。Bentley在他的著作《Writing Correct Programs》中寫(xiě)道，90%的計(jì)算機(jī)專(zhuān)家不能在2小時(shí)內(nèi)寫(xiě)出完全正確的二分搜索算法。問(wèn)題的關(guān)鍵在于準(zhǔn)確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數(shù)的各種情況，其實(shí)整理后可以發(fā)現(xiàn)它的具體算法是很直觀的。

算法步驟給予一個(gè)包含n個(gè)帶值元素的數(shù)組A或是記錄A0...An?1，使得A0≤ ... ≤An?1，以及目標(biāo)值T，還有下列用來(lái)搜索T在A中位置的子程序。

令L為0，R為n? 1。

如果L>R，則搜索以失敗告終。

令m（中間值元素）為“(L+R) / 2”加上下高斯符號(hào)。

如果AmT，令R為m- 1并回到步驟二。

當(dāng)Am=T，搜索結(jié)束；回傳值m。

這個(gè)迭代步驟會(huì)持續(xù)通過(guò)兩個(gè)變量追蹤搜索的邊界。有些實(shí)際應(yīng)用會(huì)在算法的最后放入相等比較，讓比較循環(huán)更快，但平均而言會(huì)多一層迭代。2

大致匹配以上程序只適用于完全匹配，也就是查找一個(gè)目標(biāo)值的位置。不過(guò)，因?yàn)橛行驍?shù)組的順序性，將二分搜索算法擴(kuò)展到能適用大致匹配并不是很重要。舉例來(lái)說(shuō)，二分搜索算法可以用來(lái)計(jì)算一個(gè)賦值的排名（或稱(chēng)秩，比它更小的元素的數(shù)量）、前趨（下一個(gè)最小元素）、后繼（下一個(gè)最大元素）以及最近鄰。搜索兩個(gè)值之間的元素?cái)?shù)目的范圍查詢(xún)可以借由兩個(gè)排名查詢(xún)（又稱(chēng)秩查詢(xún)）來(lái)運(yùn)行。

排名查詢(xún)可以使用調(diào)整版的二分搜索來(lái)運(yùn)行。借由在成功的搜索回傳m，以及在失敗的搜索回傳L，就會(huì)取而代之地回傳了比起目標(biāo)值小的元素?cái)?shù)目。

前趨和后繼查詢(xún)可以借由排名查詢(xún)來(lái)運(yùn)行。一旦知道目標(biāo)值的排名，其前趨就會(huì)是那個(gè)位于其排名位置的元素（因?yàn)樗切∮谀繕?biāo)值的最大元素）。其后繼是（數(shù)組中的）下一個(gè)元素，或是（非數(shù)組中的）前趨的下一個(gè)元素。目標(biāo)值的最近鄰可能是前趨或后繼，取決于何者較為接近。

范圍查詢(xún)也是直接了當(dāng)?shù)?。一旦知道兩個(gè)值的排名，不小于第一個(gè)值且小于第二個(gè)值的元素?cái)?shù)量就會(huì)是兩者排名的差。這個(gè)值可以根據(jù)范圍的端點(diǎn)是否算在范圍內(nèi)，或是數(shù)組是否包含其端點(diǎn)的對(duì)應(yīng)鍵來(lái)增加或減少1。

代碼我們可用C++描述如下：

template

int BinarySearch(Type a[],const Type& x,int n)

{

int left=0;

int right=n-1;

while(lefta[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

或者：

/*找到目標(biāo)值時(shí)返回值為下標(biāo)，找不到時(shí)返回如果要加入此數(shù)，應(yīng)該放置的下標(biāo)（負(fù)數(shù)表示）*/

int binarySearch (int arrays[], int size, int num)

{

int low = 0, high = size - 1;

while ( high > low )

{

int mid = (low + high) / 2;

if ( num > arrays[mid] )

low = mid + 1;

else if (num

high = mid - 1;

else if (num == arrays[mid])

return mid;

}

return -low - 1;

}

第一個(gè)模板函數(shù)BinarySearch在a[0]