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