module Bisect
A direct port of the Python bisect standard library.
svn.python.org/view/python/branches/py3k/Lib/bisect.py?view=markup&pathrev=70846
Public Class Methods
Return the index where to insert item x in list a, assuming a is sorted.
The return value i is such that all e in a have e < x, and all e in a have e >= x. So if x already appears in the list, a.insert(x) will insert just before the leftmost x already there.
Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched.
# File lib/bisect.rb, line 63 def bisect_left(a, x, lo=0, hi=a.size) raise ArgumentError, "lo must be non-negative" if lo < 0 while lo < hi mid = (lo + hi) / 2 if a[mid] < x lo = mid + 1 else hi = mid end end lo end
Return the index where to insert item x in list a, assuming a is sorted.
The return value i is such that all e in a have e <= x, and all e in a have e > x. So if x already appears in the list, a.insert(x) will insert just after the rightmost x already there.
Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched.
# File lib/bisect.rb, line 28 def bisect_right(a, x, lo=0, hi=a.size) raise ArgumentError, "lo must be non-negative" if lo < 0 while lo < hi mid = (lo + hi) / 2 if x < a[mid] hi = mid else lo = mid + 1 end end lo end
Insert item x in list a, and keep it sorted assuming a is sorted.
If x is already in a, insert it to the left of the leftmost x.
Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched.
# File lib/bisect.rb, line 50 def insort_left(a, x, lo=0, hi=a.size) index = bisect_left(a, x, lo, hi) a.insert(index, x) end
Insert item x in list a, and keep it sorted assuming a is sorted.
If x is already in a, insert it to the right of the rightmost x.
Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched.
# File lib/bisect.rb, line 14 def insort_right(a, x, lo=0, hi=a.size) index = bisect_right(a, x, lo, hi) a.insert(index, x) end