home *** CD-ROM | disk | FTP | other *** search
/ PC World 2001 April / PCWorld_2001-04_cd.bin / Software / TemaCD / webclean / !!!python!!! / BeOpen-Python-2.0.exe / BISECT.PY < prev    next >
Encoding:
Python Source  |  2000-09-28  |  590 b   |  24 lines
  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
  24.