# Bsearch.rb

**URL:** <https://www.ruby-forum.com/t/bsearch-rb/178996>\
**Category:** Ruby\
**Created:** [November 15, 2009, 11:35am UTC](https://www.ruby-forum.com/t/bsearch-rb/178996 "2009-11-15T11:35:11Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![ralphshnelvar](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/r/e19adc/32.png) [@ralphshnelvar](https://www.ruby-forum.com/u/ralphshnelvar)\
**Post date:** [November 15, 2009, 11:35am UTC](https://www.ruby-forum.com/t/bsearch-rb/178996/1 "2009-11-15T11:35:11Z")

</div>

I found online [Ruby/Bsearch: a binary search library for Ruby](http://0xcc.net/ruby-bsearch/). Yippee!

Is the following good idiomatic Ruby for doing a binary search the way  
that Array.assoc searches linearly?

irb -r .\ruby-bsearch-1.5\bsearch.rb

sorted\_array = [  
[1, [1000, rand(1000), rand(1000)]],  
[2, [ 999, rand(1000), rand(1000)]],  
[4, [ 998, rand(1000), rand(1000)]],  
[5, [ 997, rand(1000), rand(1000)]],  
[7, [ 887, rand(1000), rand(1000)]],  
[9, [ 886, rand(1000), rand(1000)]],  
[11, [400, rand(1000), rand(1000)]],  
[12, [300, rand(1000), rand(1000)]],  
]

module My\_Bsearch  
def my\_bsearch(i)  
bs = self.bsearch\_first {|x| x[0] \<=\> i}  
return bs unless bs  
self[bs][1]  
end  
end

sorted\_array.extend My\_Bsearch

sorted\_array.my\_bsearch(5)  
sorted\_array.my\_bsearch(15)

generates

irb(main):001:0\> sorted\_array = [  
irb(main):002:1\* [1, [1000, rand(1000), rand(1000)]],  
irb(main):003:1\* [2, [ 999, rand(1000), rand(1000)]],  
irb(main):004:1\* [4, [ 998, rand(1000), rand(1000)]],  
irb(main):005:1\* [5, [ 997, rand(1000), rand(1000)]],  
irb(main):006:1\* [7, [ 887, rand(1000), rand(1000)]],  
irb(main):007:1\* [9, [ 886, rand(1000), rand(1000)]],  
irb(main):008:1\* [11, [400, rand(1000), rand(1000)]],  
irb(main):009:1\* [12, [300, rand(1000), rand(1000)]],  
irb(main):010:1\* ]  
=\> [[1, [1000, 29, 372]], [2, [999, 707, 33]], [4, [998, 93, 630]], [5,  
[997, 25  
1, 454]], [7, [887, 863, 250]], [9, [886, 729, 534]], [11, [400, 121,  
908]], [12  
, [300, 849, 504]]]  
irb(main):011:0\>  
irb(main):012:0\*  
irb(main):013:0\* module My\_Bsearch  
irb(main):014:1\> def my\_bsearch(i)  
irb(main):015:2\> bs = self.bsearch\_first {|x| x[0] \<=\> i}  
irb(main):016:2\> return bs unless bs  
irb(main):017:2\> self[bs][1]  
irb(main):018:2\> end  
irb(main):019:1\> end  
=\> nil  
irb(main):020:0\>  
irb(main):021:0\*  
irb(main):022:0\* sorted\_array.extend My\_Bsearch  
=\> [[1, [1000, 29, 372]], [2, [999, 707, 33]], [4, [998, 93, 630]], [5,  
[997, 25  
1, 454]], [7, [887, 863, 250]], [9, [886, 729, 534]], [11, [400, 121,  
908]], [12  
, [300, 849, 504]]]  
irb(main):023:0\>  
irb(main):024:0\* sorted\_array.my\_bsearch(5)  
=\> [997, 251, 454]  
irb(main):025:0\> sorted\_array.my\_bsearch(15)  
=\> nil  
irb(main):026:0\>