发布于 2016-08-09 10:58:36 | 49 次阅读 | 评论: 0 | 来源: 网友投递

这里有新鲜出炉的Ruby教程,程序狗速度看过来!

Ruby编程语言

Ruby,一种为简单快捷的面向对象编程(面向对象程序设计)而创的脚本语言,在20世纪90年代由日本人松本行弘开发,遵守GPL协议和Ruby License。它的灵感与特性来自于 Perl、Smalltalk、Eiffel、Ada以及 Lisp 语言。


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

在计算机科学中,二分搜索(英语: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实现二分搜索(二分查找)算法的简单示例
Ruby程序中发送基于HTTP协议的请求的简单示例
Ruby实现的最优二叉查找树算法
Ruby实现的各种排序算法
Ruby实现的矩阵连乘算法
Ruby实现的合并排序算法
Ruby实现的最长公共子序列算法
Ruby实现的3种快速排序算法
ruby实现的插入排序和冒泡排序算法
冒泡排序算法及Ruby版的简单实现
Ruby实现插入排序算法及进阶的二路插入排序代码示例
Ruby实现的图片滤镜算法代码
最新网友评论  共有(0)条评论 发布评论 返回顶部
月排行榜

Copyright © 2007-2017 PHPERZ.COM All Rights Reserved   冀ICP备14009818号  版权声明  服务