二進位制搜尋與其他搜尋模式有什麼不同?
Context:當插入和刪除操作與檢索交錯時,使用二進位制搜尋的排序陣列是一個非常低效的解決方案,  每個這樣的操作的時間. 此外,排序的陣列可以使記憶體使用複雜化,特別是當元素經常被插入陣列時. 其他資料結構支援更高效的插入和刪除. 二進位制搜尋可用於執行精確匹配和集合成員 (確定目標值是否在值集合中). 有資料結構支援更快的準確匹配和集合成員. 然而,與許多其他搜尋方案不同,二進位制搜尋可以用於高效的近似匹配,通常在 不論價值本身的型別或結構. 此外,還有一些操作,比如找到最小和最大的元素,可以在排序的陣列上高效地執行.  線性搜尋:  線性搜尋是一種簡單的搜尋演算法, 檢查每個記錄, 直到找到目標值. 可以在連結列表上進行線性搜尋,這允許比陣列更快地插入和刪除. 二進位制搜尋比線性搜尋對排序的陣列更快,除非陣列很短,儘管陣列需要事先進行排序. 所有基於比較元素的排序演算法,如快速排序和合並排序,至少需要 在最糟糕的情況下進行比較. 與線性搜尋不同,二進位制搜尋可以用於高效的近似匹配. 有一些操作,比如找到最小和最大的元素,可以在排序陣列中有效地執行,但不能在未排序陣列中執行.  樹木:  二進位制搜尋樹的搜尋使用類似於二進位制搜尋的演算法. 二進位制搜尋樹是一個基於二進位制搜尋原理的二進位制樹資料結構. 樹的記錄是按排序排列的,樹中的每個記錄可以使用類似於二進位制搜尋的演算法進行搜尋,使用平均對數時間. 在二進位制搜尋樹中,插入和刪除也需要平均對數時間. 這可以比線性時間插入和刪除排序陣列快,二進位制樹保留在排序陣列上執行所有可能的操作的能力,包括範圍和近似查詢.  然而,二進位制搜尋通常對搜尋更有效,因為二進位制搜尋樹很可能不完美平衡,導致比二進位制搜尋的效能稍差一些. 這甚至適用於平衡的二進位制搜尋樹, 平衡自己的節點的二進位制搜尋樹, 因為它們很少產生最少可能的層次的樹. 除了平衡的二進位制搜尋樹外,樹可能嚴重失衡,內部節點很少,有兩個子節點,導致平均和最差的搜尋時間接近 n比較.[e]二進位制搜尋樹比排序陣列佔用更多空間.  二進位制搜尋樹適用於快速搜尋儲存在硬碟上的外部記憶體,因為二進位制搜尋樹可以在檔案系統中高效地結構化. B-樹將這種樹組織方法概括為: B-樹經常用於組織長期儲存,例如資料庫和檔案系統.  標籤: 對於實現關聯陣列,雜湊表,一個使用雜湊函式將鍵對映到記錄的資料結構,通常比對排序的記錄陣列進行二進位制搜尋更快.大多數雜湊表實現只需要平均攤銷常數時間.然而,雜湊對近似匹配不有用,例如計算下一個最小,下一個最大和最近的鍵,因為在失敗的搜尋中所提供的唯一資訊是目標不在任何記錄中. 對於這樣的匹配,二進位制搜尋是理想的, 二進位制搜尋也支援近似匹配. 有些操作,比如找到最小和最大的元素,可以在排序陣列上有效地執行,但不能在雜湊表上.  設定會員演算法: 與搜尋相關的問題是集合成員. 任何搜尋演算法,比如二進位制搜尋, 也可以用於集合成員. 還有其他演算法更適合整合. 在鍵的範圍有限時, 位陣列是最簡單的, 它緊<unk>地儲存一組位,每個位代表一個單一的鍵在鍵的範圍. 位陣列非常快,只需要 在Judy1型別的Judy陣列中,可以有效處理64位鍵.  對於近似結果,基於雜湊的另一個概率資料結構Bloom過<unk>器通過使用位陣列和多個雜湊函式來編碼一組金鑰來儲存. 在大多數情況下,Bloom過<unk>器比位元陣列更有效地使用空間,並且不太慢: k 雜湊函式,成員查詢只需要 時間. 然而, 布魯姆<unk>波器有錯誤的陽性.  其他資料結構: 有一些資料結構可以在某些情況下改善二進位制搜尋,既可以用於搜尋,也可以用於對排序陣列的其他操作. 例如,搜尋,近似匹配和對排序陣列可用的操作可以比對二進位制搜尋在專業資料結構上更有效地執行,例如範·埃德·博斯樹,融合樹,試驗和位陣列. 這些專門的資料結構通常只能更快,因為它們利用具有特定屬性的金鑰 (通常是小整數的金鑰) 的屬性,因此對於缺乏該屬性的金鑰來說,會耗費時間或空間. 只要可以對鍵進行排序,這些操作總是可以在排序的陣列上至少有效地執行, 不管鍵是什麼. 一些結構,如Judy陣列,使用多種方法的組合來減輕這種情況,同時保持效率和執行近似匹配的能力.
當插入和刪除操作與檢索交錯時, 帶有二進位制搜尋的排序陣列是一個非常低效的解決方案. 此外,排序的陣列可以使記憶體使用複雜化,特別是當元素經常被插入陣列時. 二進位制搜尋比線性搜尋對排序的陣列更快,除非陣列很短,儘管陣列需要事先進行排序. 二進位制搜尋通常更有效,因為二進位制搜尋樹很可能不完美平衡,導致比二進位制搜尋效能稍差. 一個使用雜湊函式對映鍵到記錄的資料結構,通常比對排序的記錄陣列進行二進位制搜尋更快.