blob: 4a4d05255e5810d5f918cd2176f915046d25e672 [file] [log] [blame]
Guido van Rossum4acc25b2000-02-02 15:10:15 +00001"""Bisection algorithms."""
Guido van Rossum4e160981992-09-02 20:43:20 +00002
Tim Peters36cdad12000-12-29 02:06:45 +00003def 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
Georg Brandl2ee470f2008-07-16 12:55:28 +000012 if lo < 0:
13 raise ValueError('lo must be non-negative')
Guido van Rossum4acc25b2000-02-02 15:10:15 +000014 if hi is None:
15 hi = len(a)
16 while lo < hi:
Guido van Rossum54e54c62001-09-04 19:14:14 +000017 mid = (lo+hi)//2
Guido van Rossum4acc25b2000-02-02 15:10:15 +000018 if x < a[mid]: hi = mid
19 else: lo = mid+1
20 a.insert(lo, x)
Guido van Rossum4e160981992-09-02 20:43:20 +000021
Tim Peters36cdad12000-12-29 02:06:45 +000022insort = insort_right # backward compatibility
Guido van Rossum4e160981992-09-02 20:43:20 +000023
Tim Peters36cdad12000-12-29 02:06:45 +000024def 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
Guido van Rossumd8faa362007-04-27 19:54:29 +000028 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.
Tim Peters36cdad12000-12-29 02:06:45 +000030
31 Optional args lo (default 0) and hi (default len(a)) bound the
32 slice of a to be searched.
33 """
34
Georg Brandl2ee470f2008-07-16 12:55:28 +000035 if lo < 0:
36 raise ValueError('lo must be non-negative')
Guido van Rossum4acc25b2000-02-02 15:10:15 +000037 if hi is None:
38 hi = len(a)
39 while lo < hi:
Guido van Rossum54e54c62001-09-04 19:14:14 +000040 mid = (lo+hi)//2
Guido van Rossum4acc25b2000-02-02 15:10:15 +000041 if x < a[mid]: hi = mid
42 else: lo = mid+1
43 return lo
Tim Peters36cdad12000-12-29 02:06:45 +000044
45bisect = bisect_right # backward compatibility
46
47def 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
Georg Brandl2ee470f2008-07-16 12:55:28 +000056 if lo < 0:
57 raise ValueError('lo must be non-negative')
Tim Peters36cdad12000-12-29 02:06:45 +000058 if hi is None:
59 hi = len(a)
60 while lo < hi:
Guido van Rossum54e54c62001-09-04 19:14:14 +000061 mid = (lo+hi)//2
Tim Peters36cdad12000-12-29 02:06:45 +000062 if a[mid] < x: lo = mid+1
63 else: hi = mid
64 a.insert(lo, x)
65
66
67def 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
Guido van Rossumd8faa362007-04-27 19:54:29 +000071 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.
Tim Peters36cdad12000-12-29 02:06:45 +000073
74 Optional args lo (default 0) and hi (default len(a)) bound the
75 slice of a to be searched.
76 """
77
Georg Brandl2ee470f2008-07-16 12:55:28 +000078 if lo < 0:
79 raise ValueError('lo must be non-negative')
Tim Peters36cdad12000-12-29 02:06:45 +000080 if hi is None:
81 hi = len(a)
82 while lo < hi:
Guido van Rossum54e54c62001-09-04 19:14:14 +000083 mid = (lo+hi)//2
Tim Peters36cdad12000-12-29 02:06:45 +000084 if a[mid] < x: lo = mid+1
85 else: hi = mid
86 return lo
Raymond Hettinger0c410272004-01-05 10:13:35 +000087
88# Overwrite above definitions with a fast C implementation
89try:
Raymond Hettinger9dbc6702009-03-31 17:51:51 +000090 from _bisect import *
Raymond Hettinger0c410272004-01-05 10:13:35 +000091except ImportError:
92 pass