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实现的合并排序算法
算法课的作业,利用分治法,合并排序. #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实现的图片滤镜算法代码
原图 一.灰度算法 彩色照片每一个像素的颜色值由红.绿.蓝三种值混合而成,红绿蓝的取值分别由很多种,于是像素的颜色值也可以有很多种颜色值,这就是彩色图片的原理,而灰度照片则只有256种颜色,一般的处理方法是将图片颜色值的RGB三个通道值设为一样,这样图片的显示效果就会是灰色. 灰度处理一般有三种算法: 最大值法:即新的颜色值R=G=B=Max(R,G,B),这种方法处理后的图片看起来亮度值偏高. 平均值法:即新的颜色值R=G=B=(R+G+B)/3,这样处理的图片十分柔和 加权平均值法:即新的颜
-
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实现的插入排序和冒泡排序算法
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实现的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实现的矩阵连乘算法
动态规划解决矩阵连乘问题,随机产生矩阵序列,输出形如((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实现的最优二叉查找树算法
算法导论上的伪码改写而成,加上导论的课后练习第一题的解的构造函数. 复制代码 代码如下: #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实现二分搜索(二分查找)算法的简单示例
在计算机科学中,二分搜索(英语: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# 二分查找算法
折半搜索,也称二分查找算法.二分搜索,是一种在有序数组中查找某一特定元素的搜索算法. A 搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束: B 如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较. C 如果在某一步骤数组为空,则代表找不到.这种搜索算法每一次比较都使搜索范围缩小一半. 时间复杂度折半搜索每次把搜索区域减少一半,时间复杂度为. (n代表集合中元素的个数)空间复杂度 复制代码 代码如下: //
-
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. 原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合
随机推荐
- 一张Web前端的思维导图分享
- JavaScript中的正则表达式解析
- 浅谈用java实现事件驱动机制
- Java语言面向对象编程思想之类与对象实例详解
- 使用js复制链接中的部分文字的方法
- php插件Xajax使用方法详解
- C语言编程时常犯十八个错误小结
- Android实现点击两次BACK键退出应用
- JS三目运算(三元运算)方法详解
- PHP检测链接是否存在的代码实例分享
- jQuery Pagination Ajax分页插件(分页切换时无刷新与延迟)中文翻译版
- 利用C++实现最长公共子序列与最长公共子串
- 最常用的12种设计模式小结
- CentOS 6.6服务器编译安装lnmp(Nginx1.6.2+MySQL5.6.21+PHP5.6.3)
- java 将方法作为传参--多态的实例
- C++实现简单的学生管理系统
- 写JQuery插件的基本知识
- JS实现仿饿了么在浏览器标签页失去焦点时网页Title改变
- 微信开发 js实现tabs选项卡效果
- Flex Builder3 官方正式版下载地址附注册码