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
