Mercurial > cpython-lru_cache-weakref

annotate Lib/bisect.py @ 5817:48b94de85bf3 legacy-trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Extensive changes by AMK.
author Guido van Rossum <guido@python.org>
date Thu, 17 Jul 1997 16:29:42 +0000
parents 903071377d29
children fb9b0d246ef3
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1006
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
1 # Bisection algorithms
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
2
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
3
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
4 # Insert item x in list a, and keep it sorted assuming a is sorted
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
5
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
6 def insort(a, x):
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
7 lo, hi = 0, len(a)
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
8 while lo < hi:
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
9 mid = (lo+hi)/2
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
10 if x < a[mid]: hi = mid
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
11 else: lo = mid+1
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
12 a.insert(lo, x)
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
13
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
14
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
15 # Find the index where to insert item x in list a, assuming a is sorted
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
16
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
17 def bisect(a, x):
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
18 lo, hi = 0, len(a)
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
19 while lo < hi:
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
20 mid = (lo+hi)/2
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
21 if x < a[mid]: hi = mid
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
22 else: lo = mid+1
903071377d29 Added a _v21 def to FL.py and added two new input field types
Guido van Rossum <guido@python.org>
parents:
diff changeset
23 return lo