Add Binary Search To Arrays In Ruby

• Tweet
• 

        A tiny snippet adding binary search to [sorted] Arrays. It returns the array index if found and nil otherwise.

class Array
  def bsearch(e, l = 0, u = length - 1)
    return if l>u;m=(l+u)/2;e<self[m]?u=m-1:l=m+1;e==self[m]?m:bsearch(e,l,u)
  end
end

usage:

(0..100).to_a.bsearch(12)
=> 12
(0..100).to_a.bsearch(-1)
=> nil
(0..100).to_a.bsearch(12, 50, 100) # defining upper and lower bound indices
=> nil

Note: this does <b>not</b> guarantee to find the lowest index occurrence of an element, only the one it hits first. If you require that safety, try <a href="http://0xcc.net/ruby-bsearch/index.html.en">ruby-bsearch</a>.    

Tags:
• Array
• binary
• find
• Ruby
• search