Skip to Content

Ruby - bsearch

Posted on

When you wanna find some special elements in an array, you can do it easily with Ruby. Ruby provides enumerables: select, reject, find, … so you can do it. But when the dataset is big, the time to find out result can be increases.

Today, I found a faster way. Array#bsearch can find a match with only O(log n) complexity.

require 'benchmark'

data = (0..50_000_000) do |x| { data.find {|number| number > 40_000_000 } } { data.bsearch {|number| number > 40_000_000 } }

         user       system     total       real
find     3.020000   0.010000   3.030000   (3.028417)
bsearch  0.000000   0.000000   0.000000   (0.000006)
comments powered by Disqus