Ruby实现二分搜索(二分查找)算法的简单示例
更新时间:2020年6月30日 23:54 点击:2786
在计算机科学中,二分搜索(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
复杂度分析
时间复杂度:
折半搜索每次把搜索区域减少一半,时间复杂度为。(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)
结果:
6 [Finished in 0.1s]
上一篇: ruby ftp封装实例详解
下一篇: Redis集群搭建全记录
相关文章
Ruby on Rails实现最基本的用户注册和登录功能的教程
这里我们主要以has_secure_password的用户密码验证功能为中心,来讲解Ruby on Rails实现最基本的用户注册和登录功能的教程,需要的朋友可以参考下...2020-06-30- 二分查找是一种在已经过排序的数组中搜索指定元素用的算法,这里我们就来看一下Ruby实现二分搜索(二分查找)算法的简单示例:...2020-06-30
- Ruby将字符串像数字一样处理.我们用单引号('...')或双引号("...")将它们括起来. ruby> "abc" "abc" ruby> 'abc' "abc" 单引号和双引号在某些情况下有不同的...2020-06-30
- Rack是一个连接Ruby程序与服务器程序之间的中间件,甚至可以说Rails也是在Rack的基础上建立起来的,这里我们就来为大家带来Ruby on Rails中Rack中间件的基础学习教程...2020-06-30
- 这篇文章主要介绍了jQuery实现查找最近父节点的方法,涉及jQuery针对元素节点操作的相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2016-06-24
- 这篇文章主要介绍了C++实现的O(n)复杂度内查找第K大数算法,结合实例形式分析了算法的原理以及具体实现方法,需要的朋友可以参考下...2020-04-25
- 钩子方法即是在普通的方法上添加"钩子",使特定事件发生时可以被调用,下面就来以实例讲解Ruby中的钩子方法及对方法调用添加钩子...2020-06-30
- 这篇文章主要介绍了python系统指定文件的查找只输出目录下所有文件及文件夹,本文给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下...2020-04-22
- 在本篇内容里小编给大家整理了关于python中二分查找法的实现方法,有需要的朋友们可以学习下。...2020-12-07
- 单件方法顾名思义,就是只作用于单个对象的方法,同理单件类就是单件方法所存在的类,规定其作用域,这里我们就来详解Ruby中的单件方法和单件类:...2020-06-30
- Dreamweaver是一款非常不错的软件设计工具了,如果你碰到在使用 Dreamweaver时 查找和替换窗口不见了我们可以来看看下面的办法。 最近用Dreamweaver8遇到了一种很...2016-10-02
- */ $str="hello world"; //定义字符串 $result=str_word_count($str); //查找单词个数 echo $result; //输出的结果 echo "<br>"; $re...2016-11-25
- gem是一种文件组织的包,一般的ruby的很多插件都有由这种各种的包提供。我们来看看gem的用法...2020-06-30
- 这篇文章主要介绍了基于java查找最长字符串代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-09-15
Ubuntu上配置Ruby on Rails框架及RubyMine IDE开发环境
Ruby on Rails是Ruby世界中当仁不让的Web框架代表,甚至可以说Rails推动了Ruby的流行,这里我们就来看一下如何在Ubuntu上配置Ruby on Rails框架及RubyMine IDE开发环境...2020-06-30- 这篇文章主要介绍了R语言 查找满足条件的数并获取索引的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-06
Ruby 中的 module_function 和 extend self异同
本文主要给大家介绍了在Ruby中 module_function 和 extend self的共同点和区别,非常的详细,也很实用,方便大家更好的理解的module_function 和 extend self...2020-06-30- 本篇文章,小编为大家介绍一下,C#中怎样从指定字符串中查找并替换字符串?有需要的朋友可以参考一下...2020-06-25
Ruby on rails安装后去掉DL is deprecated,please use Fiddle警告信息的方法【测试可用】
这篇文章主要介绍了Ruby on rails安装后去掉DL is deprecated,please use Fiddle警告信息的方法,通过针对Ruby on rails安装文件中的警告部分源码进行注释来达到消除警告的目的,需要的朋友可以参考下...2020-06-30- 这篇文章主要介绍了ruby ftp封装实例详解的相关资料,需要的朋友可以参考下...2020-06-30