Binärer Algorithmus für das Halbieren eines Arrays

Dieses Modul implementiert die sortierte Warteschlangenliste, um die Sortierung nach dem Einfügen von Elementen aufrechtzuerhalten. Bei einer Liste mit großen Datenmengen ist das Einfügen und Sortieren von Elementen sehr rechenintensiv. Dieses Modul implementiert den Bisect-Algorithmus, der hauptsächlich auf der Grundlage des Binäralgorithmus implementiert wird.

bisect.bisect_left(a, x, lo=0, hi=len(a))

Element x in geordnete Liste a einfügen, die Reihenfolge unverändert lassen und den eingefügten Ort zurückgeben. Die Parameter lo und hi stellen den Bereich der Beurteilungsliste dar, und der Standardwert ist der gesamte Bereich. Wenn das eingefügte Element x bereits in Liste a vorhanden ist, wird es links vom vorhandenen Element eingefügt.

Beispiel:

#Python 3.4

bisect importieren

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

print(bisect.bisect_left(l, 0))

print(l)

print(bisect.bisect_left(l, 5))

print(bisect.bisect_left(l, 7))

Die Ergebnisausgabe ist wie folgt:

[3 , 5, 6, 6, 8]

0

[3, 5, 6, 6, 8]

1

4

bisect.bisect_right(a, x, lo=0, hi=len(a))

bisect.bisect(a, x, lo=0, hi =len( a))

Finden Sie die Position, an der x in die geordnete Warteschlange a eingefügt werden kann, und halten Sie die Warteschlange in Ordnung. Wenn der eingefügte Wert mit dem Wert in der Warteschlange übereinstimmt, wird er rechts neben demselben Element eingefügt und der Indexwert dieser Position zurückgegeben.

Beispiel:

#python 3.4

bisect importieren

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

print(bisect.bisect_right(l, 0))

print(l)

print(bisect.bisect(l, 5))

print(bisect.bisect(l, 7))

Die Ergebnisausgabe ist wie folgt:

[3 , 5, 6, 6, 8]

0

[3, 5, 6, 6, 8]

2

4

bisect.insort_left(a, x, lo=0, hi=len(a))

Ein Element x in Warteschlange a einfügen und die Warteschlange sortieren. Es sollte äquivalent sein zu: a.insert(bisect.bisect_left(a, x, lo, hi), x).

Beispiel:

#python 3.4

bisect importieren

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

bisect.insort_left(l, 0)

print(l)

bisect.insort_left(l, 5)

print(l)

bisect.insort_left(l, 7)

print(l)

Ergebnis Die Ausgabe ist wie folgt:

[3, 5, 6, 6, 8]

[0, 3, 5, 6, 6, 8]

[0 , 3, 5, 5, 6, 6, 8]

[0, 3, 5, 5, 6, 6, 7, 8]

halbieren. insort_right(a , x, lo=0, hi=len(a))

bisect.insort(a, x, lo=0, hi=len(a))

Element einfügen x in a Wenn in der Warteschlange dasselbe Element gefunden wird, wird es rechts neben demselben Element eingefügt.

Beispiel:

#python 3.4

bisect importieren

l = [8, 5, 6, 6, 3]

l.sort()

print(l)

bisect.insort_right(l, 0)

print(l)

bisect.insort(l, 5)

print(l)

bisect.insort(l, 7)

print(l)

result Die Ausgabe ist wie folgt:

[3, 5, 6, 6, 8]

[0, 3, 5, 6, 6, 8]

[0 , 3, 5, 5, 6, 6, 8]

[0, 3, 5, 5, 6, 6, 7, 8]

Verwenden Sie die obige Funktion Einige einfache Kapselung:

def index(a, x):

'Suchen Sie den Wert ganz links, der genau x entspricht'

i = bisect_left(a, x)

if i != len(a) and a[i] == x:

return i

raise ValueError

def find_lt(a, x):

'Wert ganz rechts finden, der kleiner als x ist'

i = bisect_left(a, x)

if i:

return a[i-1]

raise ValueError

def find_le(a, x):

'Finde den Wert ganz rechts kleiner als oder gleich x'

i = bisect_right(a, x)

wenn i:

a[i-1] zurückgibt

ValueError erhöhen

def find_gt(a, x):

'Finde den Wert ganz links, der größer als x ist'

i = bisect_right(a, x)

if i != len(a):

return a[i]

raise ValueError

def find_ge(a, x):

'Finde das Element ganz links, das größer oder gleich ist zu x'

i = bisect_left(a, x)

if i != len(a):

return a[i]

raise ValueError

Zum Konvertieren von Schülernoten in ABCDF-Noten verwenden:

#python 3.4

import halbect

def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):

i = bisect.bisect(breakpoints, score)

return grades [ i]

print([33, 99, 77, 70, 89, 90, 100])

print([note(score) für Partitur in [33, 99, 77, 70 , 89, 90, 100]])

Die Ergebnisausgabe ist wie folgt:

[33, 99, 77, 70, 89, 90, 100]

[ 'F', 'A', 'C', 'C', 'B', 'A', 'A']