Ruby實(shí)現(xiàn)二分搜索(二分查找)算法的簡(jiǎn)單示例
更新時(shí)間：2016年07月02日 17:19:05 作者：lucifercn
二分查找是一種在已經(jīng)過(guò)排序的數(shù)組中搜索指定元素用的算法,這里我們就來(lái)看一下Ruby實(shí)現(xiàn)二分搜索(二分查找)算法的簡(jiǎn)單示例:
在計(jì)算機(jī)科學(xué)中，二分搜索（英語(yǔ)：binary search），也稱(chēng)折半搜索（英語(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ù)雜度：
雖以遞歸形式定義，但是尾遞歸，可改寫(xiě)為循環(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]
相關(guān)文章
聽(tīng)到代碼塊這個(gè)翻譯,你或許會(huì)聯(lián)想到類(lèi)或者結(jié)構(gòu)體,但block并不是這些東西,這里就帶著大家來(lái)深入理解Ruby中的代碼塊block特性2016-05-05
本文給大家分享的是使用ruby實(shí)現(xiàn)的幾種圖片濾鏡的算法，包括灰度、二值、底片、浮雕。非常的簡(jiǎn)單實(shí)用，有需要的小伙伴可以參考下2017-01-01
用實(shí)際代碼演示Ruby的容易被誤解的6個(gè)特性
這篇文章主要介紹了用實(shí)際代碼演示Ruby的容易被誤解的6個(gè)特性,采集自IBM官方網(wǎng)站的開(kāi)發(fā)者文檔,需要的朋友可以參考下2015-04-04
快速正確的安裝 Ruby, Rails 運(yùn)行環(huán)境
對(duì)于新入門(mén)的開(kāi)發(fā)者，如何安裝 Ruby, Ruby Gems 和 Rails 的運(yùn)行環(huán)境可能會(huì)是個(gè)問(wèn)題，本頁(yè)主要介紹如何用一條靠譜的路子快速安裝 Ruby 開(kāi)發(fā)環(huán)境2014-07-07
在Mac OS X下安裝Ruby運(yùn)行環(huán)境的詳細(xì)步驟
這篇文章主要給大家介紹了在Mac OS X下安裝Ruby運(yùn)行環(huán)境的方法步驟，文中介紹的很詳細(xì)，相信對(duì)大家具有一定的參考價(jià)值，需要的朋友們下面來(lái)一起看看吧。2017-02-02
這篇文章主要介紹了Ruby中類(lèi)變量和實(shí)例變量的比較,本文講解了4點(diǎn)類(lèi)變量和實(shí)例變量的不同之處,并給出了代碼實(shí)例,需要的朋友可以參考下2015-05-05
這篇文章主要介紹了Ruby中的鉤子方法詳解,本文講解了什么是鉤子方法、included、Devise中的 included、extended、ActiveRecord中的 extended、prepended、inherited等內(nèi)容,需要的朋友可以參考下2015-05-05
這篇文章主要介紹了Rails實(shí)現(xiàn)字段加密存儲(chǔ)的方法以及具體的示例代碼，非常實(shí)用,需要的朋友可以參考下2017-11-11
這篇文章主要介紹了詳細(xì)解析Ruby中的變量,是Ruby學(xué)習(xí)中最基礎(chǔ)的知識(shí)之一,需要的朋友可以參考下2015-05-05
ruby 雜項(xiàng)...2007-11-11