在計算機科學中，二分搜索（英語：binary search），也稱折半搜索（英語：half-interval search）、對數搜索（英語：logarithmic search），是一種在有序數組中查找某一特定元素的搜索算法。搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；如果某一特定元素大于或者小于中間元素，則在數組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。
復雜度分析
時間復雜度：
折半搜索每次把搜索區域減少一半，時間復雜度為
。（n代表集合中元素的個數）
空間復雜度：
雖以遞歸形式定義，但是尾遞歸，可改寫為循環。
Ruby代碼示例
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
def binseaech(arr, i) low, high = 0, arr.size - 1 while (low < high) mid = (low + high)/2 if arr[mid] < i low = mid + 1 elsif arr[mid] > i high = mid - 1 else return mid end endendarr = [1,3,12,34,35,46,91,108]puts binseaech(arr, 91) |
結果：
|
1
2
|
6[Finished in 0.1s] |
