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

  • 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)


=> 12
=> 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="">ruby-bsearch</a>.