bsearch.rb

Discussion in 'Ruby' started by Ralph Shnelvar, Nov 15, 2009.

  1. 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>
     
    Ralph Shnelvar, Nov 15, 2009
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Artie Gold

    Re: bsearch in C

    Artie Gold, Aug 7, 2003, in forum: C Programming
    Replies:
    0
    Views:
    412
    Artie Gold
    Aug 7, 2003
  2. Richard Heathfield

    Re: bsearch in C

    Richard Heathfield, Aug 7, 2003, in forum: C Programming
    Replies:
    0
    Views:
    411
    Richard Heathfield
    Aug 7, 2003
  3. Eric Sosman

    Re: bsearch in C

    Eric Sosman, Aug 7, 2003, in forum: C Programming
    Replies:
    9
    Views:
    518
    Richard Heathfield
    Aug 12, 2003
  4. Ramprasad A Padmanabhan

    a small bsearch example

    Ramprasad A Padmanabhan, Oct 28, 2003, in forum: C Programming
    Replies:
    1
    Views:
    3,794
    Mark Gordon
    Oct 28, 2003
  5. Ramprasad A Padmanabhan

    bsearch script segfault

    Ramprasad A Padmanabhan, Dec 4, 2003, in forum: C Programming
    Replies:
    11
    Views:
    500
    Ramprasad A Padmanabhan
    Dec 5, 2003
Loading...

Share This Page