Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > bsearch.rb

Reply
Thread Tools

bsearch.rb

 
 
Ralph Shnelvar
Guest
Posts: n/a
 
      11-15-2009
I found online 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>




 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off




Advertisments