Instantly share code, notes, and snippets.

# mvj3/.gitignore Last active Sep 25, 2015

 binary_search.rbc

# 面试时候如何用Ruby写一个最短二分查找代码

```puts binary_search((1..15).to_a, 8) == 7
puts binary_search((1..15).to_a, 1) == 0
puts binary_search((1..15).to_a, 14) == 13
puts binary_search([2,3,8,15], 8) == 2```

```def binary_search array, value, from = nil, to = nil
return nil if array.blank?

from ||= 0
to   ||= array.size
mid_idx = ((from + to) / 2.0).round
mid_val = array[mid_idx]

if value == mid_val
return mid_idx
elsif value > mid_val
binary_search array, value, (mid_idx+1), to
else
binary_search array, value, from, (mid_idx-1)
end
end```

```def binary_search array, value
@idx = nil

loop do
@from ||= 0
@to   ||= (array.size - 1)

return nil if array[@from..@to].blank?

puts "+ #{@from + @to}"
@idx = ((@from + @to) / 2.0).round
puts "[#{@from}, #{@to}] #{@idx}"
#binding.pry

mid_val = array[@idx]

if value == mid_val
break
elsif value > mid_val
@from = @idx.round
break if value == array[((@from + @to) / 2.0).round]
else
@to = @idx.round
break if value == array[((@from + @to) / 2.0).ceil]
end
end

return @idx
end```

```def binary_search array, value
puts "查找数组 #{array}, 值 #{value}" if ENV["DEBUG"]
from, to, idx = 0, array.size.pred, nil
loop do
return nil if array[from..to].blank?

idx = (from + to) / 2
mid_val = array[idx]
puts "起始 #{from}, 终止 #{to}, 当前索引 #{idx}"  if ENV["DEBUG"]

if value == mid_val
break
elsif value > mid_val
from = idx + 1
else
to = idx - 1
end
end

return idx
end```

```class Array
def iterative_bindex element, lower = 0, upper = length - 1
while upper >= lower
mid = (upper + lower) / 2
if self[mid] < element
lower = mid + 1
elsif self[mid] > element
upper = mid - 1
else
return mid
end
end

return nil
end
end```

 # 二分查找（又称折半查找）是在一个有序表里查找元素的复杂度为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; ilen; i++) { if (RTEST(rb_yield(RARRAY(ary)->ptr[i]))) { return LONG2NUM(i); } } return Qnil; } rb_scan_args(argc, argv, "01", &val); for (i=0; ilen; i++) { if (rb_equal(RARRAY(ary)->ptr[i], val)) return LONG2NUM(i); } return Qnil; }

### chenyukang commented Jan 11, 2014

 Ruby默认实现为什么是遍历查找的？慢啊。
Owner

### mvj3 commented Sep 23, 2014

 @chenyukang 因为Ruby不能保证你的Array是排序过的。在没排序的Array里进行二分查找，会因为跳跃而导致找不到那个真正要找的元素。