bisect, bsearch

pythonから引っ張ってくる

class Array
  
  def insert_right(item, lo=0, hi=nil)

    if lo < 0
        raise IndexError.new('lo must be non-negative')
    end
    if hi == nil
        hi = self.length
    end
    while lo < hi
        mid = ((lo+hi)/2).truncate
        if item < self[mid]
          hi = mid
        else 
          lo = mid+1
        end
    end
    self.insert(lo, item)
  end

  def bsearch_right(item, lo=0, hi=nil)

    if lo < 0
        raise IndexError.new('lo must be non-negative')
    end
    if hi == nil
        hi = self.length
    end
    while lo < hi
        mid = ((lo+hi)/2).truncate
        if item < self[mid]
          hi = mid
        else
          lo = mid+1
        end
    end
    return lo
  end
  
  def insert_left(item, lo=0, hi=nil)

    if lo < 0
        raise IndexError.new('lo must be non-negative')
    end
    if hi == nil
        hi = self.length
    end
    while lo < hi
        mid = ((lo+hi)/2).truncate
        if self[mid] < item 
          lo = mid+1
        else
          hi = mid
        end
    end
    self.insert(lo, item)
  end

  def bsearch_left(item, lo=0, hi=nil)

    if lo < 0
        raise IndexError.new('lo must be non-negative')
    end
    if hi == nil
        hi = self.length
    end
    while lo < hi
        mid = ((lo+hi)/2).truncate
        if self[mid] < item
          lo = mid+1
        else
          hi = mid
        end
    end
    return lo
  end
end

先頭が小さくなる。逆も考えてComparetorみたいなの渡す方法のがいいのか。
bsearchはよく境界線（？）を引くのに使う

点数に応じてランク付けをするサンプル。

grades = "FEDCBA"
breakpoints = [30, 44, 66, 75, 85] 
grade = lambda do |total|
  return grades[breakpoints.bsearch_right(total)]
end 
        
p grade.call(66) #=> 'C'

p [33, 99, 77, 44, 12, 88].map{|x|
      grade.call(x)
} #=> ["E", "A", "B", "D", "F", "A"]   

以上、渋谷の駅前のマックからお届けしました！！
（今週は９時ぐらい〜10時ぐらいまで渋谷の駅前のマックでコードを書いてます）