数码控科技猎奇Iphone动漫星座游戏电竞lolcosplay王者荣耀攻略allcnewsBLOGNEWSBLOGASKBLOGBLOGZSK全部技术问答问答技术问答it问答代码软件新闻开发博客电脑/网络手机/数码笔记本电脑互联网操作系统软件硬件编程开发360产品资源分享电脑知识文档中心IT全部全部分类 全部分类技术牛文全部分类教程最新 网页制作cms教程平面设计媒体动画操作系统网站运营网络安全服务器教程数据库工具网络安全软件教学vbscript正则表达式javascript批处理更多»编程更新教程更新游戏更新allitnewsJava 新闻网络医疗信息化安全创业站长电商科技访谈域名会议专栏创业动态融资创投创业学院 / 产品经理创业公司人物访谈营销 开发数据库服务器系统虚拟化云计算 嵌入式移动开发作业作业1常见软件all电脑网络手机数码生活游戏体育运动明星影音休闲爱好文化艺术社会民生教育科学医疗健康金融管理情感社交地区其他电脑互联网软件硬件编程开发360相关产品手机平板其他电子产品摄影器材360硬件通讯智能设备购物时尚生活常识美容塑身服装服饰出行旅游交通汽车购房置业家居装修美食烹饪单机电脑游戏网页游戏电视游戏桌游棋牌游戏手机游戏小游戏掌机游戏客户端游戏集体游戏其他游戏体育赛事篮球足球其他运动球类运动赛车健身运动运动用品影视娱乐人物音乐动漫摄影摄像收藏宠物幽默搞笑起名花鸟鱼虫茶艺彩票星座占卜书画美术舞蹈小说图书器乐声乐小品相声戏剧戏曲手工艺品历史话题时事政治就业职场军事国防节日风俗法律法规宗教礼仪礼节自然灾害360维权社会人物升学入学人文社科外语资格考试公务员留学出国家庭教育学习方法语文物理生物工程学农业数学化学健康知识心理健康孕育早教内科外科妇产科儿科皮肤科五官科男科整形中医药品传染科其他疾病医院两性肿瘤科创业投资企业管理财务税务银行股票金融理财基金债券保险贸易商务文书国民经济爱情婚姻家庭烦恼北京上海重庆天津黑龙江吉林辽宁河北内蒙古山西陕西宁夏甘肃青海新疆西藏四川贵州云南河南湖北湖南山东江苏浙江安徽江西福建广东广西海南香港澳门台湾海外地区

Ruby实现二分搜索(二分查找)算法的简单示例

日期:2016/7/19 9:23:00 来源:本网整理
s">

Ruby实现二分搜索(二分查找)算法的简单示例

作者:lucifercn 字体:[增加 减小] 类型:转载 时间:2016-07-02 我要评论

二分查找是一种在已经过排序的数组中搜索指定元素用的算法,这里我们就来看一下Ruby实现二分搜索(二分查找)算法的简单示例: ">

在计算机科学中,二分搜索(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

复杂度分析
时间复杂度:
折半搜索每次把搜索区域减少一半,时间复杂度为201672171630230.png (57×31)。(n代表集合中元素的个数)
空间复杂度:
201672171655530.png (39×25)虽以递归形式定义,但是尾递归,可改写为循环。

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 on Rails框架程序连接MongoDB的教程
  • Ubuntu上配置Ruby on Rails框架及RubyMine IDE开发环境
  • 浅谈Ruby on Rails下的rake与数据库数据迁移操作
  • Ruby环境下安装使用bundler来管理多版本的gem
  • 详解Ruby中的单件方法和单件类
  • Ruby面向对象编程中类的方法与类的扩展
  • 实例讲解Ruby中的钩子方法及对方法调用添加钩子
  • Ruby on Rails中Rack中间件的基础学习教程
  • Ruby中钩子方法的运用实例解析
  • Ruby实现插入排序算法及进阶的二路插入排序代码示例
  • 免责声明 - 关于我们 - 联系我们 - 广告联系 - 友情链接 - 帮助中心 - 频道导航
    Copyright © 2017 www.zgxue.com All Rights Reserved