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