summaryrefslogtreecommitdiffstats
path: root/Lib/bisect.py
diff options
context:
space:
mode:
authorGuido van Rossum <guido@python.org>1992-09-02 20:43:20 (GMT)
committerGuido van Rossum <guido@python.org>1992-09-02 20:43:20 (GMT)
commit4e16098ce74c645cf1d69566b6f8bc96031554b7 (patch)
tree919ce6e774608fbf5a2e4745472e9fbc445139e9 /Lib/bisect.py
parent2179945eec5ab32b4aa88b9f7a9308a898cde8a5 (diff)
downloadcpython-4e16098ce74c645cf1d69566b6f8bc96031554b7.zip
cpython-4e16098ce74c645cf1d69566b6f8bc96031554b7.tar.gz
cpython-4e16098ce74c645cf1d69566b6f8bc96031554b7.tar.bz2
Added a _v21 def to FL.py and added two new input field types
Added runcall(func, *args) interfaces to profile.py, bdb.py, pdb.py, wdb.py Added new module bisect.py and used it in sched.py. Mostly cosmetic changes to profile.py (changed output format).
Diffstat (limited to 'Lib/bisect.py')
-rw-r--r--Lib/bisect.py23
1 files changed, 23 insertions, 0 deletions
diff --git a/Lib/bisect.py b/Lib/bisect.py
new file mode 100644
index 0000000..688666a
--- /dev/null
+++ b/Lib/bisect.py
@@ -0,0 +1,23 @@
+# Bisection algorithms
+
+
+# Insert item x in list a, and keep it sorted assuming a is sorted
+
+def insort(a, x):
+ lo, hi = 0, len(a)
+ while lo < hi:
+ mid = (lo+hi)/2
+ if x < a[mid]: hi = mid
+ else: lo = mid+1
+ a.insert(lo, x)
+
+
+# Find the index where to insert item x in list a, assuming a is sorted
+
+def bisect(a, x):
+ lo, hi = 0, len(a)
+ while lo < hi:
+ mid = (lo+hi)/2
+ if x < a[mid]: hi = mid
+ else: lo = mid+1
+ return lo