Lib/bisect.py

   1 """Bisection algorithms."""
   2
   3
   4 def insort(a, x, lo=0, hi=None):
   5     """Insert item x in list a, and keep it sorted assuming a is sorted."""
   6     if hi is None:
   7         hi = len(a)
   8     while lo < hi:
   9         mid = (lo+hi)/2
  10         if x < a[mid]: hi = mid
  11         else: lo = mid+1
  12     a.insert(lo, x)
  13
  14
  15 def bisect(a, x, lo=0, hi=None):
  16     """Find the index where to insert item x in list a, assuming a is sorted."""
  17     if hi is None:
  18         hi = len(a)
  19     while lo < hi:
  20         mid = (lo+hi)/2
  21         if x < a[mid]: hi = mid
  22         else: lo = mid+1
  23     return lo