DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Add Binary Search To Arrays In Ruby

06.03.2010
| 5703 views |
  • submit to reddit
        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>.