二分搜尋法

二分搜尋法

二分搜尋法，它充分利用了元素間的次序關係，採用分治策略，可在最壞的情況下用O(log n)完成搜尋任務。它的基本思想是，將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，算法運算終止。

基本介紹

  • 中文名：二分搜尋法
  • 外文名：dichotomous search method
  • 利用：元素間的次序關係
  • 策略：分治策略
  • 條件：在有序的元素中進行
  • 出現時間：1962年
  • 目的：搜尋信息
  • 套用學科：計算機學 數學
簡介,算法,步驟,大致匹配,代碼,複雜度計算,套用,

簡介

在計算機科學中，二分搜尋（英語：binary search），也稱折半搜尋（英語：half-interval search）、對數搜尋（英語：logarithmic search），是一種在有序數組中查找某一特定元素的搜尋算法。搜尋過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜尋過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜尋算法每一次比較都使搜尋範圍縮小一半。
如果x<a[n/2]，則我們只要在數組a的左半部繼續搜尋x（這裡假設數組元素呈升序排列）。如果x>a[n/2]，則我們只要在數組a的右半部繼續搜尋x。二分搜尋法的套用極其廣泛，而且它的思想易於理解，但是要寫一個正確的二分搜尋算法也不是一件簡單的事。第一個二分搜尋算法早在1946年就出現了，但是第一個完全正確的二分搜尋算法直到1962年才出現。Bentley在他的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內寫出完全正確的二分搜尋算法。問題的關鍵在於準確地制定各次查找範圍的邊界以及終止條件的確定，正確地歸納奇偶數的各種情況，其實整理後可以發現它的具體算法是很直觀的。

算法

步驟

給予一個包含n個帶值元素的數組A或是記錄A0...An−1，使得A0≤ ... ≤An−1，以及目標值T，還有下列用來搜尋T在A中位置的子程式。
  1. 令L為0，R為n− 1。
  2. 如果L>R，則搜尋以失敗告終。
  3. 令m（中間值元素）為“(L+R) / 2”加上下高斯符號。
  4. 如果Am<T，令L為m+ 1並回到步驟二。
  5. 如果Am>T，令R為m- 1並回到步驟二。
  6. 當Am=T，搜尋結束；回傳值m。
這個疊代步驟會持續通過兩個變數追蹤搜尋的邊界。有些實際套用會在算法的最後放入相等比較，讓比較循環更快，但平均而言會多一層疊代。

大致匹配

以上程式只適用於完全匹配，也就是查找一個目標值的位置。不過，因為有序數組的順序性，將二分搜尋算法擴展到能適用大致匹配並不是很重要。舉例來說，二分搜尋算法可以用來計算一個賦值的排名（或稱秩，比它更小的元素的數量）、前趨（下一個最小元素）、後繼（下一個最大元素）以及最近鄰。搜尋兩個值之間的元素數目的範圍查詢可以藉由兩個排名查詢（又稱秩查詢）來運行。
  • 排名查詢可以使用調整版的二分搜尋來運行。藉由在成功的搜尋回傳m，以及在失敗的搜尋回傳L，就會取而代之地回傳了比起目標值小的元素數目。
  • 前趨和後繼查詢可以藉由排名查詢來運行。一旦知道目標值的排名，其前趨就會是那個位於其排名位置的元素（因為它是小於目標值的最大元素）。其後繼是（數組中的）下一個元素，或是（非數組中的）前趨的下一個元素。目標值的最近鄰可能是前趨或後繼，取決於何者較為接近。
  • 範圍查詢也是直接了當的。一旦知道兩個值的排名，不小於第一個值且小於第二個值的元素數量就會是兩者排名的差。這個值可以根據範圍的端點是否算在範圍內，或是數組是否包含其端點的對應鍵來增加或減少1。

代碼

我們可用C++描述如下：
template<class Type>
int BinarySearch(Type a[],const Type& x,int n)
{
int left=0;
int right=n-1;
while(left<=right){
int middle=(left+right)/2;
if (x==a[middle]) return middle;
if (x>a[middle]) left=middle+1;
else right=middle-1;
}
return -1;
}
或者：
/*找到目標值時返回值為下標，找不到時返回如果要加入此數，應該放置的下標（負數表示）*/
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 < arrays[mid])
high = mid - 1;
else if (num == arrays[mid])
return mid;
}
return -low - 1;
}
第一個模板函式BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n個升序排列的元素中搜尋x,找到x時返回其在數組中的位置，否則返回-1。容易看出，每執行一次while循環，待搜尋數組的大小減少一半,因此整個算法在最壞情況下的時間複雜度為O(log n)。在數據量很大的時候，它的線性查找在時間複雜度上的優劣一目了然。
二分搜尋法的局限性：必須是在有序的元素中進行，不能在無序的元素中使用。

複雜度計算

時間複雜度：二分搜尋每次把搜尋區域砍掉一半，很明顯時間複雜度為O(log n)。（n代表集合中元素的個數）
空間複雜度：O（1）。雖遞歸形式定義，但是尾遞歸，可改寫為循環。

套用

除直接在一個中數組查找元素外，可用在插入排序中。

熱門詞條

聯絡我們