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

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

原理計(jì)算步驟 給予一個(gè)包含 個(gè)帶值元素的數(shù)組 或是記錄，使 ，以及目標(biāo)值 ，還有下列用來搜索 在 中位置的子程序。

令 為 ， 為 。

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

令 （中間值元素）為 。

如果 ，令 為 并回到步驟二。

如果 ，令 為 并回到步驟二。

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

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

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

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

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

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

復(fù)雜度分析時(shí)間復(fù)雜度

折半搜索每次把搜索區(qū)域減少一半，時(shí)間復(fù)雜度為 。（n代表集合中元素的個(gè)數(shù)）

空間復(fù)雜度

，雖以遞歸形式定義，但是尾遞歸，可改寫為循環(huán)。

示例代碼C 版本- 遞歸int binary_search(const int arr[], int start, int end, int khey) {if (start > end)return -1; int mid = start + (end - start) / 2; //直接平均可能會(huì)溢位，所以用此算法if (arr[mid] > khey)return binary_search(arr, start, mid - 1, khey);else if (arr[mid] khey)return this.binary_search(low, mid - 1, khey);if (this[mid] end:return -1mid = start + (end - start) / 2if arr[mid] > hkey:return binary_search(arr, start, mid - 1, hkey)if arr[mid]