14acc25bd392216c4f867a10ca8081e7c8a739676Guido van Rossum"""Bisection algorithms.""" 24e16098ce74c645cf1d69566b6f8bc96031554b7Guido van Rossum 336cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Petersdef insort_right(a, x, lo=0, hi=None): 436cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters """Insert item x in list a, and keep it sorted assuming a is sorted. 536cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters 636cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters If x is already in a, insert it to the right of the rightmost x. 736cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters 836cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters Optional args lo (default 0) and hi (default len(a)) bound the 936cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters slice of a to be searched. 1036cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters """ 1136cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters 123cd1e42dca01308a9f5897ba2efc2aab0bebb661Raymond Hettinger if lo < 0: 133cd1e42dca01308a9f5897ba2efc2aab0bebb661Raymond Hettinger raise ValueError('lo must be non-negative') 144acc25bd392216c4f867a10ca8081e7c8a739676Guido van Rossum if hi is None: 154acc25bd392216c4f867a10ca8081e7c8a739676Guido van Rossum hi = len(a) 164acc25bd392216c4f867a10ca8081e7c8a739676Guido van Rossum while lo < hi: 1754e54c6877329e105406c48490f218faff59db39Guido van Rossum mid = (lo+hi)//2 184acc25bd392216c4f867a10ca8081e7c8a739676Guido van Rossum if x < a[mid]: hi = mid 194acc25bd392216c4f867a10ca8081e7c8a739676Guido van Rossum else: lo = mid+1 204acc25bd392216c4f867a10ca8081e7c8a739676Guido van Rossum a.insert(lo, x) 214e16098ce74c645cf1d69566b6f8bc96031554b7Guido van Rossum 2236cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Petersinsort = insort_right # backward compatibility 2336cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters 2436cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Petersdef bisect_right(a, x, lo=0, hi=None): 2536cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters """Return the index where to insert item x in list a, assuming a is sorted. 2636cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters 2736cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters The return value i is such that all e in a[:i] have e <= x, and all e in 287352cf5935cea97e7c5ab136a0bfa82b4af0bd06Raymond Hettinger a[i:] have e > x. So if x already appears in the list, a.insert(x) will 297352cf5935cea97e7c5ab136a0bfa82b4af0bd06Raymond Hettinger insert just after the rightmost x already there. 3036cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters 3136cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters Optional args lo (default 0) and hi (default len(a)) bound the 3236cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters slice of a to be searched. 3336cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters """ 344e16098ce74c645cf1d69566b6f8bc96031554b7Guido van Rossum 353cd1e42dca01308a9f5897ba2efc2aab0bebb661Raymond Hettinger if lo < 0: 363cd1e42dca01308a9f5897ba2efc2aab0bebb661Raymond Hettinger raise ValueError('lo must be non-negative') 374acc25bd392216c4f867a10ca8081e7c8a739676Guido van Rossum if hi is None: 384acc25bd392216c4f867a10ca8081e7c8a739676Guido van Rossum hi = len(a) 394acc25bd392216c4f867a10ca8081e7c8a739676Guido van Rossum while lo < hi: 4054e54c6877329e105406c48490f218faff59db39Guido van Rossum mid = (lo+hi)//2 414acc25bd392216c4f867a10ca8081e7c8a739676Guido van Rossum if x < a[mid]: hi = mid 424acc25bd392216c4f867a10ca8081e7c8a739676Guido van Rossum else: lo = mid+1 434acc25bd392216c4f867a10ca8081e7c8a739676Guido van Rossum return lo 4436cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters 4536cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Petersbisect = bisect_right # backward compatibility 4636cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters 4736cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Petersdef insort_left(a, x, lo=0, hi=None): 4836cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters """Insert item x in list a, and keep it sorted assuming a is sorted. 4936cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters 5036cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters If x is already in a, insert it to the left of the leftmost x. 5136cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters 5236cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters Optional args lo (default 0) and hi (default len(a)) bound the 5336cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters slice of a to be searched. 5436cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters """ 5536cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters 563cd1e42dca01308a9f5897ba2efc2aab0bebb661Raymond Hettinger if lo < 0: 573cd1e42dca01308a9f5897ba2efc2aab0bebb661Raymond Hettinger raise ValueError('lo must be non-negative') 5836cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters if hi is None: 5936cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters hi = len(a) 6036cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters while lo < hi: 6154e54c6877329e105406c48490f218faff59db39Guido van Rossum mid = (lo+hi)//2 6236cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters if a[mid] < x: lo = mid+1 6336cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters else: hi = mid 6436cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters a.insert(lo, x) 6536cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters 6636cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters 6736cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Petersdef bisect_left(a, x, lo=0, hi=None): 6836cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters """Return the index where to insert item x in list a, assuming a is sorted. 6936cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters 7036cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters The return value i is such that all e in a[:i] have e < x, and all e in 717352cf5935cea97e7c5ab136a0bfa82b4af0bd06Raymond Hettinger a[i:] have e >= x. So if x already appears in the list, a.insert(x) will 727352cf5935cea97e7c5ab136a0bfa82b4af0bd06Raymond Hettinger insert just before the leftmost x already there. 7336cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters 7436cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters Optional args lo (default 0) and hi (default len(a)) bound the 7536cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters slice of a to be searched. 7636cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters """ 7736cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters 783cd1e42dca01308a9f5897ba2efc2aab0bebb661Raymond Hettinger if lo < 0: 793cd1e42dca01308a9f5897ba2efc2aab0bebb661Raymond Hettinger raise ValueError('lo must be non-negative') 8036cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters if hi is None: 8136cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters hi = len(a) 8236cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters while lo < hi: 8354e54c6877329e105406c48490f218faff59db39Guido van Rossum mid = (lo+hi)//2 8436cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters if a[mid] < x: lo = mid+1 8536cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters else: hi = mid 8636cdad12ddb2d70cc260d2a03e2b7e2f8ebb9a73Tim Peters return lo 870c4102760c440af3e7b575b0fd27fe25549641a2Raymond Hettinger 880c4102760c440af3e7b575b0fd27fe25549641a2Raymond Hettinger# Overwrite above definitions with a fast C implementation 890c4102760c440af3e7b575b0fd27fe25549641a2Raymond Hettingertry: 903476d1279f469125c62bcea8a84ab65c1e271152Raymond Hettinger from _bisect import * 910c4102760c440af3e7b575b0fd27fe25549641a2Raymond Hettingerexcept ImportError: 920c4102760c440af3e7b575b0fd27fe25549641a2Raymond Hettinger pass 93