home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 1999 August / SGI Freeware 1999 August.iso / dist / fw_python.idb / usr / freeware / lib / python1.5 / bisect.py.z / bisect.py
Encoding:
Text File  |  1999-04-16  |  480 b   |  26 lines
  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
  26.