Lib/bisect.py

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