0001 """Bisection algorithms.""" 0002 0003 def insort_right(a, x, lo=0, hi=None): 0004 """Insert item x in list a, and keep it sorted assuming a is sorted. 0005 0006 If x is already in a, insert it to the right of the rightmost x. 0007 0008 Optional args lo (default 0) and hi (default len(a)) bound the 0009 slice of a to be searched. 0010 """ 0011 0012 if hi is None: 0013 hi = len(a) 0014 while lo < hi: 0015 mid = (lo+hi)//2 0016 if x < a[mid]: hi = mid 0017 else: lo = mid+1 0018 a.insert(lo, x) 0019 0020 insort = insort_right # backward compatibility 0021 0022 def bisect_right(a, x, lo=0, hi=None): 0023 """Return the index where to insert item x in list a, assuming a is sorted. 0024 0025 The return value i is such that all e in a[:i] have e <= x, and all e in 0026 a[i:] have e > x. So if x already appears in the list, i points just 0027 beyond the rightmost x already there. 0028 0029 Optional args lo (default 0) and hi (default len(a)) bound the 0030 slice of a to be searched. 0031 """ 0032 0033 if hi is None: 0034 hi = len(a) 0035 while lo < hi: 0036 mid = (lo+hi)//2 0037 if x < a[mid]: hi = mid 0038 else: lo = mid+1 0039 return lo 0040 0041 bisect = bisect_right # backward compatibility 0042 0043 def insort_left(a, x, lo=0, hi=None): 0044 """Insert item x in list a, and keep it sorted assuming a is sorted. 0045 0046 If x is already in a, insert it to the left of the leftmost x. 0047 0048 Optional args lo (default 0) and hi (default len(a)) bound the 0049 slice of a to be searched. 0050 """ 0051 0052 if hi is None: 0053 hi = len(a) 0054 while lo < hi: 0055 mid = (lo+hi)//2 0056 if a[mid] < x: lo = mid+1 0057 else: hi = mid 0058 a.insert(lo, x) 0059 0060 0061 def bisect_left(a, x, lo=0, hi=None): 0062 """Return the index where to insert item x in list a, assuming a is sorted. 0063 0064 The return value i is such that all e in a[:i] have e < x, and all e in 0065 a[i:] have e >= x. So if x already appears in the list, i points just 0066 before the leftmost x already there. 0067 0068 Optional args lo (default 0) and hi (default len(a)) bound the 0069 slice of a to be searched. 0070 """ 0071 0072 if hi is None: 0073 hi = len(a) 0074 while lo < hi: 0075 mid = (lo+hi)//2 0076 if a[mid] < x: lo = mid+1 0077 else: hi = mid 0078 return lo 0079 0080 # Overwrite above definitions with a fast C implementation 0081 try: 0082 from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect 0083 except ImportError: 0084 pass 0085
Generated by PyXR 0.9.4