Prev: How do I get a random number between two random numbers?
Next: what's ||
From: Ralph Shnelvar on 15 Nov 2009 05:34
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>




 | 
Pages: 1
Prev: How do I get a random number between two random numbers?
Next: what's ||