Binary Search(二分搜尋)

摘要： 轉載請註明出處 http://leonchen1024.com/2018/08/14/Binary-Search/ 二分搜尋(binary search),也叫做 折半搜尋(half-interval search),對數搜尋(logarithmic search),對半搜尋(bina...

轉載請註明出處 ofollow,noindex">http://leonchen1024.com/2018/08/14/Binary-Search/

二分搜尋(binary search),也叫做 折半搜尋(half-interval search),對數搜尋(logarithmic search),對半搜尋(binary chop),是一種在有序陣列中查詢某一特定元素的搜尋演算法.

二分搜尋有幾個變體.特別是,分散層疊( fractional cascading )(將每個數組裡的值集合成一個數組,元素為11[0,3,2,0] 的形式,括號內的數字是該值在對應陣列中應該返回的數字)提高了在多個數組中查詢相同值的效率,高效的解決了一系列計算幾何和其他領域的查詢問題).指數查詢( Exponential search )延伸了二分查詢到一個沒有邊界的 list. binary search tree 和 B-tree 是基於 binary search 延伸的.

原理

搜尋時從陣列中間元素開始,如果中間元素正好是要查詢的元素,則搜尋過程結束;如果中間元素大於或者小於要查詢的元素,則在陣列中大於或者小於查詢元素的一半中繼續查詢,重複這個過程直到找到這個元素,或者這一半的大小為空時則代表找不到.這樣子每一次比較都使得搜尋範圍縮小一半.

步驟

給定一個有序陣列 A 是 A0,...,An-1並保證 A0<=...<=An-1,以及目標值 T.

1. 令 L 為0,R 為 n-1.
2. 如果 L>R 則搜尋失敗
3. 令m(中間值元素索引)為最大的小於(L+R)/2的整數
4. 如果 Am<T ,令 L=m+1並回到第2步;
5. 如果 Am>T ,令 R=m-1並回到第2步;
6. 當 Am=T,搜尋結束;T 所在的索引位置為m.

變體

1. 令 L 為0,R 為 n-1.
2. 令 m(中間元素索引) 為上限,也就是最小的大於(L+R)/2的值.
3. 如果 Am>T ,設定 R 為 m-1並且返回第2步
4. 如果 Am<=T ,設定 L 為m 並且返回第2步.
5. 直到 L=R ,搜尋完成.這時候如果T=Am,返回 m,否則,搜尋失敗.

轉載請註明出處 http://leonchen1024.com/2018/08/14/Binary-Search/

在 Am<=T 的時候,這個變體將 L 設定為 m 而不是 m+1.這個方式的比較是更快速的,因為它在每個迴圈裡省略了一次比較.但是平均就會多出來一次迴圈.在陣列包含重複的元素的時候這個變體總是會返回最右側的元素索引.比如 A 是[1,2,3,4,4,5,6,7]查詢的物件是4,那麼這個方法會返回 index 4,而不是 index 3.

大致匹配

由於有序陣列的順序性,可以將二分搜尋擴充套件到大致匹配.可以用來計算賦值的排名(或稱秩,比它更小的元素的數量),前趨(下一個最小元素),後繼(下一個最大元素)以及最近鄰.還可以使用兩個排名查詢來執行範圍查詢.

• 排名查詢可以使用調整後的二分搜尋來進行.成功時返回m,失敗時返回 L, 這樣就等於返回了比目標值小的元素數目.
• 前趨和後繼可以使用排名查詢來進行.當知道目標值的排名,成功時前趨是排名位置的上一個元素,失敗時則是排名位置的元素.它的後繼是排名位置的後一個元素,或是前趨的下一個元素.目標值的最近領可能是前趨或後繼,取決於哪個更接近目標值.
• 範圍查詢,一旦知道範圍兩邊的值的排名,那麼大於邊界最小值且小於邊界最大值的元素排名就是他們的範圍,是否包含邊界值根據需要處理.

效能分析

綜合複雜度為

分散層疊(fractional cascading) 可以提高在多陣列中查詢相同值的效率. k 是陣列的數量,在每個陣列中查詢目標值消耗 的時間.分散層疊可以將它降低到 .

變體效率分析
相對於正常的二分搜尋,它減少了每次迴圈的比對次數,但是它必須做完完整的迴圈,而不會在中間就得到答案.但是在 n 很大的情況下減少了對比次數的提升不能夠抵消多餘的迴圈的消耗.

轉載請註明出處 http://leonchen1024.com/2018/08/14/Binary-Search/

空間複雜度

O(1).尾遞迴,可以改寫為迴圈.

應用

查詢陣列中的元素,或用於插入排序.

二分搜尋和其他的方案對比

使用二分搜尋的有序陣列在插入和刪除操作效率很低,每個操作消耗 O(n) 的時間.其他的資料結構提供了更高效的插入和刪除,並且提供了同樣高效的完全匹配.然而,二分搜尋適用於很多的搜尋問題,只消耗 的時間.

Hashing

對於 關聯陣列 (associative arrays) , 雜湊表 (hash tables) ,他們是通過hash 函式將鍵對映到記錄上的資料結構,通常情況下比在有序陣列的情況下使用二分查詢要更快.大部分的實現平均開銷都是常量級的.然而, hashing 並不適用於模糊匹配,比如計算前趨,後繼,以及最近的鍵,它在失敗的查詢情況下能給我們的唯一資訊就是目標在記錄中不存在.二分查詢是這種匹配的理想模式,消耗對數級別的時間.

Trees

二叉搜尋樹(binary search tree) 是一個基於二叉搜尋原理的二叉樹(binary tree)資料結構.樹的記錄按照順序排列,並且每個樹裡的每個記錄都可以使用類似二叉搜尋的方法來搜尋,平均耗費對數級的時間.插入和刪除的平均時間也是對數級的.這會比有序陣列消耗的線性時間要快,並且二叉樹擁有所有有序陣列可以執行的操作,包含範圍和模糊查詢.

然而二叉搜尋通常情況下比二叉搜尋樹的搜尋更有效率,因為二叉搜尋樹很可能會完全不平衡,導致效能稍差.這同樣適用於 平衡二叉搜尋樹( balanced binary search trees) , 它平衡了它自己的節點稍微向完全平衡樹靠攏.雖然不太可能,但是樹有可能只有少數節點有兩個子節點導致嚴重不平衡,這種情況下平均時間損耗和最差的情況差不多都是 O(n) .二叉搜尋樹比有序陣列佔用更多的空間.

二叉搜尋樹因為可以高效的在檔案系統中結構化,所以他們可以在硬碟中進行快速搜尋.B-tree 泛化了這種樹結構的方法.B-tree 常用於組織長時間的儲存比如資料庫(databases)和 檔案系統(filesystems) .

Linear search

線性搜尋( Linear Search) 是一種簡單的搜尋演算法,它查詢每一個記錄直到找到目標值.線性搜尋可以在 連結串列(linked list) 上使用,它的插入和刪除會比在陣列上要快.二分搜尋比線性搜尋要快除非陣列很短.如果陣列必須先被排序,這個消耗必須在搜尋中平攤.對陣列進行排序還可以進行有效的近似匹配和其他操作.

Set membership algorithms

一個和搜尋相關的問題是 集合成員(set membership) .所有有關查詢的演算法,比如二分搜尋,都可以用於集合成員.還有一些更適用於集合成員的演算法,位陣列(bit array)是最簡單的一個,在鍵的範圍是有限的時候非常有用.它非常快,是需要O(1)的時間.朱迪矩陣(Judy array)可以高效的處理64位鍵.

對於近似結果, 布隆過濾器(Bloom filters) 是另外一個基於雜湊的概率性資料結構,通過儲存使用bit array 和多重 hash 函式編碼的鍵集合. Bloom filters 在大多數情況下空間效率比bit arrays 要高而不會慢太多:使用了 k 重hash 函式,成員查詢只需要 O(k) 的時間.然而, Bloom filters 有一定的誤判性.

其他的資料結構

轉載請註明出處 http://leonchen1024.com/2018/08/14/Binary-Search/

這裡存在一些資料結構在某些情況下比在有序陣列上使用二分搜尋進行查詢或其他的操作更加高效.比如,在van Emde Boas trees, fusion trees ,字首樹(tries), 和位陣列 上進行查詢,近似匹配,以及其他可用的操作可以比在有序陣列上進行二分搜尋更加的高效.然而,儘管這些操作可以比在無視鍵的情況下比有序陣列上使用更高效,這樣的資料結構通常是因為利用了某些鍵的屬性(鍵通常是一些小整數),因此如果鍵缺乏那些屬性將會消耗更多的空間或時間.一些結構如朱迪矩陣,使用了多種方式的組合來保證效率和執行近似匹配的能力.

變體

Uniform binary search

Uniform binary search 不是儲存下限和上限的邊界值,而是中間元素的索引,和從這次迴圈的中間元素到下次迴圈的中間元素的變化.每一步的變化減少一半.比如,要搜尋的陣列是[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],中間元素是6.Uniform binary search 同時對左邊和右邊的子陣列進行操作.在這個情況下,左邊的子陣列([1, 2, 3, 4, 5]) 的中間元素 3 而右邊的子陣列 ([7, 8, 9, 10, 11]) 的中間元素是 9.然後儲存3 作為兩個中間元素和 6 的差別.為了減少搜尋的空間使用,演算法同時加上或減去這個和中間元素的改變.這個演算法的好處是可以將每次迴圈的索引的差別儲存到一個表裡,在某些系統裡可以提高演算法的效能.

Exponential search

Interpolation search

內插搜尋(Interpolation search)忽略了目標值的位置,計算陣列的最低和最高元素的距離即陣列的長度.這隻有在陣列元素是數字的時候才能使用.它適用於中間值不是最好的猜測選擇的情況.比如,如果目標值接近陣列的最高元素,最好是定位在陣列的末端.如果陣列的分佈是均勻的或者接近均勻的,它消耗 次比較.

實際上,內插搜尋在陣列元素較少的情況下是比二分搜尋更慢的,因為內插搜尋需要額外的計算.儘管它的時間複雜度增長是小於二分搜尋的,只有在在大陣列的情況下這個計算的損耗可以被彌補.

Fractional cascading

分散層疊(Fractional cascading) 可以提高在多個有序數組裡查詢相同的元素或近似匹配的效率,分別在每個數組裡查詢總共需要 的時間, k 是陣列的數量.分散層疊通過將每個陣列的資訊按指定的方式儲存起來將這個時間降低到 .

轉載請註明出處 http://leonchen1024.com/2018/08/14/Binary-Search/

它將每個數組裡的值集合成一個數組,元素為 11[0,3,2,0] 的形式,括號內的數字是該值在對應陣列中應該返回的數字)提高了在多個數組中查詢相同值的效率,高效的解決了一系列計算幾何和其他領域的查詢問題

分散層疊被髮明的時候是為了高效的解決各種 計算幾何學(computational geometry) 問題,但是它同樣適用於其他地方,例如 資料探勘(data mining) 和 網際網路協議(Internet Protocal) 等.

實現時的問題

要注意中間值的取值方法,如果使用 (L+R)/2 當陣列的元素數量很大的時候回造成計算溢位.所以要使用L+(R-L)/2.

示例

C 版本- 遞迴

int binary_search(const int arr[], int start , int end , int khey){
if (start > end)
return -1;

int mid = start +(end - start)/2;//直接平均可能會溢位,所以用此演算法
if (arr[mid] > khey)
return binary_search(arr , start , mid - 1 , khey);
else if (arr[mid] < khey)
return binary_search(arr , mid + 1 , end , khey);
else
return mid;//最後才檢測相等的情況是因為大多數搜尋情況不是大於就是小於

}

C 版本- while 迴圈

int binary_search(const int arr[], int start, int end, int khey){
int result = -1;//如果沒有搜尋到資料返回 -1

int mid;
while (start <= end){
mid = start + (end - start)/2 ;//直接平均可能會溢位,所以用此演算法
if (arr[mid] > khey)
end = mid-1;
else if (arr[mid] < khey)
start = mid + 1;
else{//最後才檢測相等的情況是因為大多數搜尋情況不是大於就是小於
result = mid;
break;
}
}

return result;

}

Python3 遞迴

def binary_search(arr, start, end, hkey):
if start > end:
return -1

mid = start + (end - start) / 2
if arr[mid] > hkey:
return binary_search(arr, start , mid - 1,hkey)
if arr[mid] < hkey:
return binary_search(arr, mid + 1, end, hkey)
return mid

Python3 while 迴圈

def binary_search(arr, start, end, hkey):
result = -1

while start <= end:
mid = start + (end - start) / 2
if arr[mid] > hkey :
end = mid - 1
elif arr[mid] < hkey :
start = mid + 1
else :
result = mid
break

return result

Java 遞迴

public static int binarySearch(int[] arr, int start, int end, int hkey){
if (start > end)
return -1;

int mid = start + (end - start)/2;//防止溢位
if (arr[mid] > hkey)
return binarySearch(arr, start, mid - 1, hkey);
if (arr[mid] < hkey)
return binarySearch(arr, mid + 1, end, hkey);
return mid;

}

Java while 迴圈

public static int binarySearch(int[] arr, int start, int end, int hkey){
int result = -1;

while (start <= end){
int mid = start + (end - start)/2;//防止溢位
if (arr[mid] > hkey)
end = mid - 1;
else if (arr[mid] < hkey)
start = mid + 1;
else {
result = mid ;
break;
}
}

return result;

}

References

https://en.wikipedia.org/wiki/Binary_search_algorithm

轉載請註明出處 http://leonchen1024.com/2018/08/14/Binary-Search/

About Me

我的部落格 leonchen1024.com

我的 GitHub https://github.com/LeonChen1024

微信公眾號

[圖片上傳失敗...(image-42c4a2-1541582448153)]