二分查找和插入
# 二分查找（又称折半查找）是在一个有序表里查找元素的复杂度为O(log(n))的算法。先从中# 二分查找（又称折半查找）是在一个有序表里查找元素的复杂度为O(log(n))的算法。先从中间位置开始比较，相等则返回，如小于中间值，则将接下来的查找范围设定为前一子表，大于则为后一子表，以下如此类推。# 维基百科参考：http://en.wikipedia.org/wiki/Binary_search_algorithmclass 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]] endendrequire 'benchmark'array = (0..6**7).to_aputs "数组是从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 putsend__END__以下是运行本程序的结果数组是从0到279936的之间的所有整数匹配-1 user system total realindex 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 realindex 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 realindex 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 realindex 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 realindex 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 VALUErb_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;}