Our Daily Method #16: Array#bsearch

Geplaatst door Michiel de Mare di, 26 feb 2008 08:00:00 GMT

Searching in arrays is pretty slow. Better use a hash.

But if the array is already sorted, you can use a binary search, which works by dividing the array in two and searching in the left orthe right part, until there’s only one element left.

class Array
  def bsearch(k)
    x,y = -1,size
    while y != x + 1 do
      m = (x + y) / 2
      if self[m] <= k
        x = m
      else
        y = m
      end
    end
    x >= 0 && self[x] == k && x
  end
end