在計(jì)算機(jī)科學(xué)中，二分搜索（英語(yǔ)：binary search），也稱折半搜索（英語(yǔ)：half-interval search）、對(duì)數(shù)搜索（英語(yǔ)：logarithmic search），是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜索過(guò)程從數(shù)組的中間元素開(kāi)始，如果中間元素正好是要查找的元素，則搜索過(guò)程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開(kāi)始一樣從中間元素開(kāi)始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。

復(fù)雜度分析
時(shí)間復(fù)雜度：
折半搜索每次把搜索區(qū)域減少一半，時(shí)間復(fù)雜度為。（n代表集合中元素的個(gè)數(shù)）
空間復(fù)雜度：
雖以遞歸形式定義，但是尾遞歸，可改寫為循環(huán)。

Ruby代碼示例

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
  end
end
arr = [1,3,12,34,35,46,91,108]
puts binseaech(arr, 91)

結(jié)果：

6
[Finished in 0.1s]

版權(quán)聲明：本站文章來(lái)源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請(qǐng)保持原文完整并注明來(lái)源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非maisonbaluchon.cn所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來(lái)源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來(lái)，僅供學(xué)習(xí)參考，不代表本站立場(chǎng)，如有內(nèi)容涉嫌侵權(quán)，請(qǐng)聯(lián)系alex-e#qq.com處理。