bisect.py (1413B)
1 #Embedded file name: C:\BuildAgent\work\20d73f1b24eed06e\eve\release\V24.01\carbon\common\stdlib\bisect.py 2 3 4 def insort_right(a, x, lo = 0, hi = None): 5 if lo < 0: 6 raise ValueError('lo must be non-negative') 7 if hi is None: 8 hi = len(a) 9 while lo < hi: 10 mid = (lo + hi) // 2 11 if x < a[mid]: 12 hi = mid 13 else: 14 lo = mid + 1 15 16 a.insert(lo, x) 17 18 19 insort = insort_right 20 21 def bisect_right(a, x, lo = 0, hi = None): 22 if lo < 0: 23 raise ValueError('lo must be non-negative') 24 if hi is None: 25 hi = len(a) 26 while lo < hi: 27 mid = (lo + hi) // 2 28 if x < a[mid]: 29 hi = mid 30 else: 31 lo = mid + 1 32 33 return lo 34 35 36 bisect = bisect_right 37 38 def insort_left(a, x, lo = 0, hi = None): 39 if lo < 0: 40 raise ValueError('lo must be non-negative') 41 if hi is None: 42 hi = len(a) 43 while lo < hi: 44 mid = (lo + hi) // 2 45 if a[mid] < x: 46 lo = mid + 1 47 else: 48 hi = mid 49 50 a.insert(lo, x) 51 52 53 def bisect_left(a, x, lo = 0, hi = None): 54 if lo < 0: 55 raise ValueError('lo must be non-negative') 56 if hi is None: 57 hi = len(a) 58 while lo < hi: 59 mid = (lo + hi) // 2 60 if a[mid] < x: 61 lo = mid + 1 62 else: 63 hi = mid 64 65 return lo 66 67 68 try: 69 from _bisect import * 70 except ImportError: 71 pass