# 二分查找(又称折半查找)是在一个有序表里查找元素的复杂度为O(log(n))的算法。先从中# 二分查找(又称折半查找)是在一个有序表里查找元素的复杂度为O(log(n))的算法。先从中间位置开始比较,相等则返回,如小于中间值,则将接下来的查找范围设定为前一子表,大于则为后一子表,以下如此类推。
# 维基百科参考:http://en.wikipedia.org/wiki/Binary_search_algorithm
class Array
# 迭代版本
def binary_search_in_iterative num, insert = true
min, max = 0, self.size - 1
while min <= max
mid = (min + max) / 2
if num < self[mid]
max = mid - 1
elsif num == self[mid]
return mid
else
min = mid + 1
end
end
insert_item num, min, mid if insert
return nil if min > max
end
# 递归版本
def binary_search_in_recursive num, insert = true, min = nil, max = nil
min ||= 0
max ||= self.size - 1
mid = (min + max) / 2
if min > max
insert_item num, min, mid if insert
return nil
end
if num > self[mid]
binary_search_in_recursive num, insert, mid + 1 , max
elsif num < self[mid]
binary_search_in_recursive num, insert, min, mid - 1
else
return mid
end
end
def insert_item num, min, mid
min = mid if self[min].nil?
self[min..min] = (self[min] < num) ? [self[min], num] : [num, self[min]]
end
end
require 'benchmark'
array = (0..6**7).to_a
puts "数组是从0到#{array[-1]}的之间的所有整数"
[-1, -6**3, 0, 4**5, 6**6].each do |num|
puts "匹配#{num}"
Benchmark.bm do |x|
x.report("index ") { array.index num }
x.report("iterative") { array.binary_search_in_iterative num, false }
x.report("recursive") { array.binary_search_in_recursive num, false }
end
puts
end
__END__
以下是运行本程序的结果
数组是从0到279936的之间的所有整数
匹配-1
user system total real
index 0.010000 0.000000 0.010000 ( 0.014947)
iterative 0.000000 0.000000 0.000000 ( 0.000048)
recursive 0.000000 0.000000 0.000000 ( 0.000065)
匹配-216
user system total real
index 0.010000 0.000000 0.010000 ( 0.014744)
iterative 0.000000 0.000000 0.000000 ( 0.000028)
recursive 0.000000 0.000000 0.000000 ( 0.000040)
匹配0
user system total real
index 0.000000 0.000000 0.000000 ( 0.000005)
iterative 0.000000 0.000000 0.000000 ( 0.000019)
recursive 0.000000 0.000000 0.000000 ( 0.000032)
匹配1024
user system total real
index 0.000000 0.000000 0.000000 ( 0.000059)
iterative 0.000000 0.000000 0.000000 ( 0.000031)
recursive 0.000000 0.000000 0.000000 ( 0.000048)
匹配46656
user system total real
index 0.000000 0.000000 0.000000 ( 0.003513)
iterative 0.000000 0.000000 0.000000 ( 0.000022)
recursive 0.000000 0.000000 0.000000 ( 0.000045)
从上面可以看到,迭代都比递归快一倍左右,不难看出Ruby里默认的数组查找是直接在线性时间里遍历查找的,查看Array#index对应的C源码一看便知。
static VALUE
rb_ary_index(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
VALUE val;
long i;
if (argc == 0) {
RETURN_ENUMERATOR(ary, 0, 0);
for (i=0; i<RARRAY(ary)->len; i++) {
if (RTEST(rb_yield(RARRAY(ary)->ptr[i]))) {
return LONG2NUM(i);
}
}
return Qnil;
}
rb_scan_args(argc, argv, "01", &val);
for (i=0; i<RARRAY(ary)->len; i++) {
if (rb_equal(RARRAY(ary)->ptr[i], val))
return LONG2NUM(i);
}
return Qnil;
}
分享到:
相关推荐
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表...
二分查找的C实现
1.二分查找又称为折半查找,它要求要查找的顺序表必须是有序表,即表中结点按关键字有序.并且要用顺序存储结构。 基本思想是:首先将给定值key与表中中间位置记录的关键字相比较,若二者相等,则查找成功,否则...
二分查找(C++):查找过程中能够记录比较元素的下标并输出 二叉排序树(C++):建立;显示结点、插入元素、删除元素。
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好,占用系统内存较少;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素...
顺序查找表 二分查找表 折半查找表 二叉排序树 C#源代码 注意二叉排序树只实现了查找和插入算法,使用Visual Studio 2008开发
二分法查找法以及和二叉树查找的联系,部分二分搜索和二叉查找树的相关题目: 插入位置;区间查找;旋转位置查找;二叉查找树的编码和解码;逆序数的解题方法和代码实现
跳表是一种既支持快速查找,又支持动态插入删除的数据结构,它通过在链表的基础上增加链来提高查找的性能。本程序用C++实现了跳表的查找,插入跟删除操作。
二叉排序树:更新二叉排序树、查找结点、插入结点、删除结点、中序输出排序树 、返回 查找算法:顺序查找、二分查找、二插排序树、返回
(1) 对下列数据表,分别采用二分查找算法实现查找,给出查找过程依次所比较的元素,并以二分查找的判定树来解释。 (2) 设计出在二叉排序树中插入结点的算法,在此基础上实现构建二叉排序树的算法。 (3) 设计算法在...
程序模拟实验所用到的所有源码,包括冒泡排序,插入排序,代码运行时长统计等。
C语言中常见的排序算法包括归并排序、选择排序、直接插入排序、希尔排序、冒泡排序、快速排序、堆排序以及顺序查找和二分查找。这些排序算法各有特点,在不同情况下有着不同的应用场景和性能表现。 归并排序(Merge...
当你需要构建一个大的有序队列,用插入发太慢了,可以先用二分查找法,找到在队列要插入的位置,把数后移一下,然后放进去。比较效率,下面是java使用示例,需要的朋友可以参考下
1 掌握查找的不同方法,并能用高级... 2 熟练掌握顺序表和有序表的顺序查找和二分查找方法。 3 掌握排序的不同方法,并能用高级语言实现排序算法。 4 熟练掌握顺序表的选择排序、冒泡排序和直接插入排序算法的实现。
<1> 对下列数据表,分别采用二分查找算法实现查找,给出查找过程依次所比较的元素(的下标),并以二分查找的判定树来解释。 <2> 设计出在二叉排序树中插入结点的算法,在此基础上实现构建二叉排序树的算法。 <3> ...
本文实例讲述了C++二分查找(折半查找)算法。分享给大家供大家参考,具体如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。 因此,折半查找...
基于平行数组与二分查找的有序符号表是《算法》中的经典查找算法,本程序使用 Python 语言,实现有序符号表。 ST.py 包含两个类,ST 和 OrderedST。 ST是无序的符号表,基于链表实现。按照顺序将键值对插入链表。 ...
搜索插入位置给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。示例 1:输入: [1,3,
查找表源码,其中包含两个独立的程序: (1)哈希(Hash)表操作测试程序 (2)二分查找法测试程序 用C语言编译器编译后可以直接运行,功能包括查找、插入、删除等操作。