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):
   7         lo, hi = 0, 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 # Find the index where to insert item x in list a, assuming a is sorted
  16
  17 def bisect(a, x):
  18         lo, hi = 0, 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