Ruby newbie, my first binary search - is this idiomatic ruby?

Hi All,

I just finished the codeacademy Ruby course, and ventured to
write a binary search in Ruby.
After years of Java , this is fun !
Let me know what you think - any feedback / tips / pointers , alternate
ways of doing the same - are welcome !!

######################################################

binary search implementation

def bsearch(a,y)
#puts " – >> #{a} #{a.length} find #{32}"
return false if a == nil
return false if a.length == 0
return false if a.length == 1 && a[0] != y
return true if a.length == 1 && a[0] == y

l  = a.length
return true if a[ l/2 ] == y
return bsearch a[ 0,l/2],y if y < a[l/2]
return bsearch a[ l/2, l],y

end

1000.times do |x|
# create an array of 100 random numbers
a = []
100.times{ |x| a.push rand(100) }
a.sort!
# set the number to search for
x = 32

    # search using our method
    contains_x =  bsearch( a, x)
    # verify using ruby's built-in include?
    check = a.include? x
    # print the verdict
    puts contains_x == check ? " you win a toaster ! " : " fail! "

end
######################################################

Looks good, so here are just a few minor things:

a = Array.new(100){rand(100)}

  • I would condense the checks a bit, and use in-built methods to check
    for nilness/emptyness:

return false if a.nil? || a.empty?
return a.first == y if a.length == 1

Btw, I got some experience with and am starting with Java at work, and
that is a lot of fun, too. Type-safety and compile-time checks do scale
nicely.

I would not call a variable ‘l’, because - depending on the font - it is
easy to mistake it as digit 1 when reading.

I think you could write bsearch more compact as

def bsearch(a,y)
  middle = (a||=[]).length / 2
  middle > 0 ?
    (y < a[middle] ? bsearch(a[0..middle],y) : 

bsearch(a[middle+1…-1]) :
(a[0]||’’) == y
end

(Code not tested, though). It is a matter of taste, which version is
more readable.

Note also that a[x,y] does not mean the array slice from element x to
element y. For this, we have a[x…y].

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs