Ruby實(shí)現(xiàn)二分搜索(二分查找)算法的簡(jiǎn)單示例
更新時(shí)間：2016年07月02日 17:19:05 作者：lucifercn
二分查找是一種在已經(jīng)過排序的數(shù)組中搜索指定元素用的算法,這里我們就來看一下Ruby實(shí)現(xiàn)二分搜索(二分查找)算法的簡(jiǎn)單示例:
在計(jì)算機(jī)科學(xué)中，二分搜索（英語：binary search），也稱折半搜索（英語：half-interval search）、對(duì)數(shù)搜索（英語：logarithmic search），是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜索過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(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]
相關(guān)文章
這篇文章主要介紹了Ruby中的數(shù)值類型以及常量,是Ruby入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-10-10
這篇文章主要介紹了Ruby簡(jiǎn)明教程之方法(Method)介紹,ruby的方法分為實(shí)例方法、類方法、函數(shù)方法等,本文分別做了講解,需要的朋友可以參考下2014-06-06
這篇文章主要介紹了在Ruby中處理日期和時(shí)間的教程,包括時(shí)間的格式化等基本用法,需要的朋友可以參考下2015-04-04
Ruby中執(zhí)行Linux shell命令的六種方法詳解
這篇文章主要介紹了Ruby中執(zhí)行Linux shell命令的六種方法詳解,這些方法包括exec、system、反引號(hào)、IO、Open3、Open4等命令,需要的朋友可以參考下2015-01-01
這篇文章主要介紹了使用C++來編寫Ruby程序擴(kuò)展的教程,本文來自于IBM官方網(wǎng)站技術(shù)文檔,需要的朋友可以參考下2015-04-04
關(guān)于Ruby on Rails路由配置的一些建議
這篇文章主要介紹了關(guān)于Ruby on Rails路由配置的一些建議,作者提出了相關(guān)代碼編寫時(shí)一些值得注意的地方,需要的朋友可以參考下2015-08-08
這篇文章主要介紹了Ruby中的數(shù)組和散列表的使用詳解,是Ruby入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-07-07
設(shè)計(jì)模式中的模板方法模式在Ruby中的應(yīng)用實(shí)例兩則
這篇文章主要介紹了設(shè)計(jì)模式中的模板方法模式在Ruby中的應(yīng)用實(shí)例兩則,經(jīng)典的項(xiàng)目經(jīng)理例子在這里又被套上用了^^需要的朋友可以參考下2016-03-03
這篇文章主要介紹了簡(jiǎn)單的Ruby中的Socket編程教程,是為Ruby on Rails學(xué)習(xí)過程當(dāng)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-04-04
這篇文章主要介紹了Ruby中對(duì)一元操作符重載實(shí)例,實(shí)例說明如何對(duì)一元操作符進(jìn)行重載,需要的朋友可以參考下2014-06-06