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]
赞 (0)

相关推荐

  • Ruby实现的图片滤镜算法代码

    Ruby实现的图片滤镜算法代码

    原图 一.灰度算法 彩色照片每一个像素的颜色值由红.绿.蓝三种值混合而成,红绿蓝的取值分别由很多种,于是像素的颜色值也可以有很多种颜色值,这就是彩色图片的原理,而灰度照片则只有256种颜色,一般的处理方法是将图片颜色值的RGB三个通道值设为一样,这样图片的显示效果就会是灰色. 灰度处理一般有三种算法: 最大值法:即新的颜色值R＝G＝B＝Max(R,G,B),这种方法处理后的图片看起来亮度值偏高. 平均值法:即新的颜色值R＝G＝B＝(R+G+B)/3,这样处理的图片十分柔和 加权平均值法:即新的颜

  • Ruby实现的最优二叉查找树算法

    算法导论上的伪码改写而成,加上导论的课后练习第一题的解的构造函数. 复制代码 代码如下: #encoding: utf-8 =begin author: xu jin date: Nov 11, 2012 Optimal Binary Search Tree to find by using EditDistance algorithm refer to <<introduction to algorithms>> example output: "k2 is the r

  • Ruby实现的矩阵连乘算法

    动态规划解决矩阵连乘问题,随机产生矩阵序列,输出形如((A1(A2A3))(A4A5))的结果. 代码: #encoding: utf-8 =begin author: xu jin, 4100213 date: Oct 28, 2012 MatrixChain to find an optimum order by using MatrixChain algorithm example output: The given array is:[30, 35, 15, 5, 10, 20, 25]

  • Ruby实现的3种快速排序算法

    刚学Ruby,正巧算法老师鼓励用不熟悉的语言来写算法,我就用Ruby吧~~ 话说Ruby可真是超厉害,好多凭直觉的方法都可以用.....无限膜拜中.... 期间我遇到了invalid multibyte char (US-ASCII)的错误,解决办法是在开头加一个#encoding:utf-8 这个错误在stackoverflow上有人问到过,某人给出的回答是 Write # encoding: utf-8 on top of that file. That changes the defaul

  • Ruby实现的合并排序算法

    算法课的作业,利用分治法,合并排序. #encoding: utf-8 #author: xu jin, 4100213 #date: Oct 27, 2012 #MergeSort #to sort an array by using MergeSort algorithm #example output: #The original array is:[4, 32, 84, 58, 49, 40, 75, 29, 82, 21, 70, 37, 70] #The sorted array i

  • ruby实现的插入排序和冒泡排序算法

    1.插入排序 复制代码 代码如下: seq = [3,4,9,0,2,5,9,7,1] 1.upto(seq.length-1) do |i|  if seq[i] < seq[i-1]    tmp = seq[i]    j = i-1    while(j>=0 && tmp<seq[j]) do      seq[j+1] = seq[j]      j=j-1    end    seq[j+1]=tmp  endend seq.each {|num| puts

  • Ruby实现的各种排序算法

    时间复杂度:Θ(n^2) Bubble sort 复制代码 代码如下: def bubble_sort(a)    (a.size-2).downto(0) do |i|      (0..i).each do |j|        a[j], a[j+1] = a[j+1], a[j] if a[j] > a[j+1]      end    end    return a  end Selection sort 复制代码 代码如下: def selection_sort(a)    b =

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

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

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

  • python实现二分查找算法

    二分查找算法:简单的说,就是将一个数组先排序好,比如按照从小到大的顺序排列好,当给定一个数据,比如target,查找target在数组中的位置时,可以先找到数组中间的数array[middle]和target进行比较,当它比target小时,那么target一定是在数组的右边,反之,则target在数组的左边,比如它比target小,则下次就可以只比较[middle+1, end]的数,继续使用二分法,将它一分为二,直到找到target这个数返回或者数组全部遍历完成(target不在数组中) 优

  • python二分查找算法的递归实现方法

    本文实例讲述了python二分查找算法的递归实现方法.分享给大家供大家参考,具体如下: 这里先提供一段二分查找的代码: def binarySearch(alist, item): first = 0 last = len(alist)-1 found = False while first<=last and not found: midpoint = (first + last)//2 if alist[midpoint] == item: found = True else: if ite

  • 二分查找算法在C/C++程序中的应用示例

    二分查找算法的思想很简单,<编程珠玑>中的描述: 在一个包含t的数组内,二分查找通过对范围的跟综来解决问题.开始时,范围就是整个数组.通过将范围中间的元素与t比较并丢弃一半范围,范围就被缩小.这个过程一直持续,直到在t被发现,或者那个能够包含t的范围已成为空.         Donald Knuth在他的<Sorting and Searching>一书中指出,尽管第一个二分查找算法早在1946年就被发表,但第一个没有bug的二分查找算法却是在12年后才被发表出来.其中常见的一个

  • c# 二分查找算法

    c# 二分查找算法

    折半搜索,也称二分查找算法.二分搜索,是一种在有序数组中查找某一特定元素的搜索算法. A 搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束: B 如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较. C 如果在某一步骤数组为空,则代表找不到.这种搜索算法每一次比较都使搜索范围缩小一半. 时间复杂度折半搜索每次把搜索区域减少一半,时间复杂度为. (n代表集合中元素的个数)空间复杂度 复制代码 代码如下: //

  • Python递归函数 二分查找算法实现解析

    Python递归函数 二分查找算法实现解析

    一.初始递归 递归函数:在一个函数里在调用这个函数本身. 递归的最大深度:998 正如你们刚刚看到的,递归函数如果不受到外力的阻止会一直执行下去.但是我们之前已经说过关于函数调用的问题,每一次函数调用都会产生一个属于它自己的名称空间,如果一直调用下去,就会造成名称空间占用太多内存的问题,于是python为了杜绝此类现象,强制的将递归层数控制在了997(只要997!你买不了吃亏,买不了上当...). 拿什么来证明这个"998理论"呢?这里我们可以做一个实验: def foo(n): pr

  • 使用PHP实现二分查找算法代码分享

    第一种方法: [二分查找要求]:1.必须采用顺序存储结构 2.必须按关键字大小有序排列. [优缺点]折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表. [算法思想]首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 复制代码 代码如下: <?

  • php实现的二分查找算法示例

    本文实例讲述了php实现的二分查找算法.分享给大家供大家参考,具体如下: <?php $arr = array(4,58,11,34,88,45,32,54,63,78); function binary($arr,$bnum) { if(is_array($arr) && count($arr) > 0) { sort($arr); $start = 0; $end = count($arr)-1; $mid = -1; while($start <= $end) {

  • PHP二分查找算法示例【递归与非递归方法】

    本文实例讲述了PHP二分查找算法.分享给大家供大家参考,具体如下: binarySearch 二分查找采用的方法比较容易理解,以数组为例: ① 先取数组中间的值floor((low+top)/2), ② 然后通过与所需查找的数字进行比较,若比中间值大,则将首值替换为中间位置下一个位置,继续第一步的操作:若比中间值小,则将尾值替换为中间位置上一个位置,继续第一步操作 ③ 重复第二步操作直至找出目标数字 比如从1,3,9,23,54 中查找数字23, 首位置为0, 尾位置为4,中间位置就为2 值为9

  • Java实现二分查找算法实例分析

    本文实例讲述了Java实现二分查找算法.分享给大家供大家参考.具体如下: 1. 前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 2. 原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合

随机推荐