blob: 152f6c7854f829ad3eca53dadb6d383220e1e1a4 [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
Guido van Rossum4acc25b2000-02-02 15:10:15 +000012 if hi is None:
13 hi = len(a)
14 while lo < hi:
Guido van Rossum54e54c62001-09-04 19:14:14 +000015 mid = (lo+hi)//2
Guido van Rossum4acc25b2000-02-02 15:10:15 +000016 if x < a[mid]: hi = mid
17 else: lo = mid+1
18 a.insert(lo, x)
Guido van Rossum4e160981992-09-02 20:43:20 +000019
Tim Peters36cdad12000-12-29 02:06:45 +000020insort = insort_right # backward compatibility
Guido van Rossum4e160981992-09-02 20:43:20 +000021
Tim Peters36cdad12000-12-29 02:06:45 +000022def bisect_right(a, x, lo=0, hi=None):
23 """Return the index where to insert item x in list a, assuming a is sorted.
24
25 The return value i is such that all e in a[:i] have e <= x, and all e in
26 a[i:] have e > x. So if x already appears in the list, i points just
27 beyond the rightmost x already there.
28
29 Optional args lo (default 0) and hi (default len(a)) bound the
30 slice of a to be searched.
31 """
32
Guido van Rossum4acc25b2000-02-02 15:10:15 +000033 if hi is None:
34 hi = len(a)
35 while lo < hi:
Guido van Rossum54e54c62001-09-04 19:14:14 +000036 mid = (lo+hi)//2
Guido van Rossum4acc25b2000-02-02 15:10:15 +000037 if x < a[mid]: hi = mid
38 else: lo = mid+1
39 return lo
Tim Peters36cdad12000-12-29 02:06:45 +000040
41bisect = bisect_right # backward compatibility
42
43def insort_left(a, x, lo=0, hi=None):
44 """Insert item x in list a, and keep it sorted assuming a is sorted.
45
46 If x is already in a, insert it to the left of the leftmost x.
47
48 Optional args lo (default 0) and hi (default len(a)) bound the
49 slice of a to be searched.
50 """
51
52 if hi is None:
53 hi = len(a)
54 while lo < hi:
Guido van Rossum54e54c62001-09-04 19:14:14 +000055 mid = (lo+hi)//2
Tim Peters36cdad12000-12-29 02:06:45 +000056 if a[mid] < x: lo = mid+1
57 else: hi = mid
58 a.insert(lo, x)
59
60
61def bisect_left(a, x, lo=0, hi=None):
62 """Return the index where to insert item x in list a, assuming a is sorted.
63
64 The return value i is such that all e in a[:i] have e < x, and all e in
65 a[i:] have e >= x. So if x already appears in the list, i points just
66 before the leftmost x already there.
67
68 Optional args lo (default 0) and hi (default len(a)) bound the
69 slice of a to be searched.
70 """
71
72 if hi is None:
73 hi = len(a)
74 while lo < hi:
Guido van Rossum54e54c62001-09-04 19:14:14 +000075 mid = (lo+hi)//2
Tim Peters36cdad12000-12-29 02:06:45 +000076 if a[mid] < x: lo = mid+1
77 else: hi = mid
78 return lo
Raymond Hettinger0c410272004-01-05 10:13:35 +000079
80# Overwrite above definitions with a fast C implementation
81try:
82 from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect
83except ImportError:
84 pass