Home | History | Annotate | Download | only in python2.7
      1 """Bisection algorithms."""
      2 
      3 def insort_right(a, x, lo=0, hi=None):
      4     """Insert item x in list a, and keep it sorted assuming a is sorted.
      5 
      6     If x is already in a, insert it to the right of the rightmost x.
      7 
      8     Optional args lo (default 0) and hi (default len(a)) bound the
      9     slice of a to be searched.
     10     """
     11 
     12     if lo < 0:
     13         raise ValueError('lo must be non-negative')
     14     if hi is None:
     15         hi = len(a)
     16     while lo < hi:
     17         mid = (lo+hi)//2
     18         if x < a[mid]: hi = mid
     19         else: lo = mid+1
     20     a.insert(lo, x)
     21 
     22 insort = insort_right   # backward compatibility
     23 
     24 def bisect_right(a, x, lo=0, hi=None):
     25     """Return the index where to insert item x in list a, assuming a is sorted.
     26 
     27     The return value i is such that all e in a[:i] have e <= x, and all e in
     28     a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
     29     insert just after the rightmost x already there.
     30 
     31     Optional args lo (default 0) and hi (default len(a)) bound the
     32     slice of a to be searched.
     33     """
     34 
     35     if lo < 0:
     36         raise ValueError('lo must be non-negative')
     37     if hi is None:
     38         hi = len(a)
     39     while lo < hi:
     40         mid = (lo+hi)//2
     41         if x < a[mid]: hi = mid
     42         else: lo = mid+1
     43     return lo
     44 
     45 bisect = bisect_right   # backward compatibility
     46 
     47 def insort_left(a, x, lo=0, hi=None):
     48     """Insert item x in list a, and keep it sorted assuming a is sorted.
     49 
     50     If x is already in a, insert it to the left of the leftmost x.
     51 
     52     Optional args lo (default 0) and hi (default len(a)) bound the
     53     slice of a to be searched.
     54     """
     55 
     56     if lo < 0:
     57         raise ValueError('lo must be non-negative')
     58     if hi is None:
     59         hi = len(a)
     60     while lo < hi:
     61         mid = (lo+hi)//2
     62         if a[mid] < x: lo = mid+1
     63         else: hi = mid
     64     a.insert(lo, x)
     65 
     66 
     67 def bisect_left(a, x, lo=0, hi=None):
     68     """Return the index where to insert item x in list a, assuming a is sorted.
     69 
     70     The return value i is such that all e in a[:i] have e < x, and all e in
     71     a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
     72     insert just before the leftmost x already there.
     73 
     74     Optional args lo (default 0) and hi (default len(a)) bound the
     75     slice of a to be searched.
     76     """
     77 
     78     if lo < 0:
     79         raise ValueError('lo must be non-negative')
     80     if hi is None:
     81         hi = len(a)
     82     while lo < hi:
     83         mid = (lo+hi)//2
     84         if a[mid] < x: lo = mid+1
     85         else: hi = mid
     86     return lo
     87 
     88 # Overwrite above definitions with a fast C implementation
     89 try:
     90     from _bisect import *
     91 except ImportError:
     92     pass
     93