FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[Original HTTPS Page]
cpython/Lib/bisect.py at 3.5 · python/cpython · GitHub
python
cpython
Repository navigation
Code
Issues
5k+
(5k+)
Pull requests
2.7k
(2.7k)
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
cpython
/
Lib
/
bisect.py
Copy path
More file actions
More file actions
Latest commit
History
History
History
92 lines (72 loc) · 2.53 KB
Breadcrumbs
cpython
/
Lib
/
bisect.py
Copy path
File metadata and controls
92 lines (72 loc) · 2.53 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
"""Bisection algorithms."""
def
insort_right
(
a
,
x
,
lo
=
0
,
hi
=
None
):
"""Insert item x in list a, and keep it sorted assuming a is sorted.
If x is already in a, insert it to the right of the rightmost x.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
if
lo
<
0
:
raise
ValueError
(
'lo must be non-negative'
)
if
hi
is
None
:
hi
=
len
(
a
)
while
lo
<
hi
:
mid
=
(
lo
+
hi
)
//
2
if
x
<
a
[
mid
]:
hi
=
mid
else
:
lo
=
mid
+
1
a
.
insert
(
lo
,
x
)
insort
=
insort_right
# backward compatibility
def
bisect_right
(
a
,
x
,
lo
=
0
,
hi
=
None
):
"""Return the index where to insert item x in list a, assuming a is sorted.
The return value i is such that all e in a[:i] have e <= x, and all e in
a[i:] have e > x. So if x already appears in the list, a.insert(x) will
insert just after the rightmost x already there.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
if
lo
<
0
:
raise
ValueError
(
'lo must be non-negative'
)
if
hi
is
None
:
hi
=
len
(
a
)
while
lo
<
hi
:
mid
=
(
lo
+
hi
)
//
2
if
x
<
a
[
mid
]:
hi
=
mid
else
:
lo
=
mid
+
1
return
lo
bisect
=
bisect_right
# backward compatibility
def
insort_left
(
a
,
x
,
lo
=
0
,
hi
=
None
):
"""Insert item x in list a, and keep it sorted assuming a is sorted.
If x is already in a, insert it to the left of the leftmost x.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
if
lo
<
0
:
raise
ValueError
(
'lo must be non-negative'
)
if
hi
is
None
:
hi
=
len
(
a
)
while
lo
<
hi
:
mid
=
(
lo
+
hi
)
//
2
if
a
[
mid
]
<
x
:
lo
=
mid
+
1
else
:
hi
=
mid
a
.
insert
(
lo
,
x
)
def
bisect_left
(
a
,
x
,
lo
=
0
,
hi
=
None
):
"""Return the index where to insert item x in list a, assuming a is sorted.
The return value i is such that all e in a[:i] have e < x, and all e in
a[i:] have e >= x. So if x already appears in the list, a.insert(x) will
insert just before the leftmost x already there.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
if
lo
<
0
:
raise
ValueError
(
'lo must be non-negative'
)
if
hi
is
None
:
hi
=
len
(
a
)
while
lo
<
hi
:
mid
=
(
lo
+
hi
)
//
2
if
a
[
mid
]
<
x
:
lo
=
mid
+
1
else
:
hi
=
mid
return
lo
# Overwrite above definitions with a fast C implementation
try
:
from
_bisect
import
*
except
ImportError
:
pass
Back
|
FazBrowse Home
|
New Git URL