二分搜尋
搜索算法 / 維基百科,自由的 encyclopedia
在電腦科學中,二分搜尋演算法(英語:binary search algorithm),也稱折半搜尋演算法(英語:half-interval search algorithm)[1]、對數搜尋演算法(英語:logarithmic search algorithm)[2],是一種在有序陣列中搜尋某一特定元素的搜尋演算法。搜尋過程從陣列的中間元素開始,如果中間元素正好是要搜尋的元素,則搜尋過程結束;如果某一特定元素大於或者小於中間元素,則在陣列大於或小於中間元素的那一半中搜尋,而且跟開始一樣從中間元素開始比較。如果在某一步驟陣列為空,則代表找不到。這種搜尋演算法每一次比較都使搜尋範圍縮小一半。
Quick Facts 二分搜尋, 概況 ...
Close
二分搜尋演算法在最壞情況(英語:Best, worst and average case)下是對數時間複雜度的,需要進行次比較操作(在此處是陣列的元素數量,是大O記號,是對數)。二分搜尋演算法使用常數空間,對於任何大小的輸入數據,演算法使用的空間都是一樣的。除非輸入數據數量很少,否則二分搜尋演算法比線性搜尋更快,但陣列必須事先被排序。儘管一些特定的、為了快速搜尋而設計的數據結構更有效(比如雜湊表),二分搜尋演算法應用面更廣。
二分搜尋演算法有許多種變種。比如分散層疊(英語:fractional casacading)可以提升在多個陣列中對同一個數值的搜尋的速度。分散層疊有效的解決了計算幾何學和其他領域的許多搜尋問題。指數搜尋(英語:Exponential search)將二分搜尋演算法拓寬到無邊界的列表。二叉搜尋樹和B樹數據結構就是基於二分搜尋演算法的。