Onze dagmethode #16: Array#bsearch

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

Zoeken in arrays is best langzaam. Gebruik liever een hash.

Maar als de array al gesorteerd is, kun je een binary search gebruiken. Die werkt door de array doormidden te delen, en vervolgens verder te zoeken in het linker of het rechter deel, net zolang totdat het element gevonden is of er nog maar een element over is..


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

Recommend Michiel de Mare

Geplaatst in ,  | 1 reactie

Reacties

Laat een reactie achter

  1. p3t0r zei ongeveer 13 uur later:

    Performance technisch is dit vast niet veel soeps… maar ik moest het gewoon proberen… een recursieve variant:

    class Array  
  def bsearch(k, first = 0, upto = self.size/2)
    if  first < upto
        mid = first + (upto - first) / 2  # Compute mid point.
        return bsearch(k, first, mid) if k < self[mid]
        return bsearch(k, mid+1, upto) if k > self[mid]
        mid # found it!
    end
  end
end

(Laat url/e-mail achter »)

   Voorvertoning