Python Bisect - Binäre Suche

1. bisect.bisect_left() Überblick
2. Anwendungen von bisect_left()
3. bisect.bisect_right() Überblick
4. Anwendungen von bisect_right()

In diesem Artikel sehen wir uns an, wie man die in Python eingebauten Module verwendet, um eine binäre Suche durchzuführen. Das Modul bisect basiert auf der Bisektionsmethode zum Finden der Wurzeln von Funktionen. Es besteht aus 6 Funktionen: bisect(), bisect_left(), bisect_right(), insort(), insort_left(), insort_right(), die uns erlauben, den Index eines Elements zu finden oder ein Element an der richtigen Position in einer Liste einzufügen. Sie helfen auch dabei, die Liste nach jedem Einfügen sortiert zu halten. Aber damit sie richtig funktionieren, müssen wir sicherstellen, dass das Array bereits sortiert ist.

bisect.bisect_left() Überblick

Diese Funktion wird verwendet, um den äußersten linken Einfügepunkt einer Zahl x innerhalb einer sortierten Liste zu finden. Wenn x bereits in der Liste vorhanden ist, dann wird das neue x an der äußersten linken Position unter allen x in der Liste eingefügt.

Syntax

bisect_left(arr, x, lo=0, hi=len(a))

Parameter

Zurück

Es wird ein Einfügepunkt zurückgegeben, der das Array in zwei Hälften partitioniert: die erste mit allen Werten kleiner als x und die zweite mit allen Werten größer als x.

Anwendungen von bisect_left()

Finden des ersten Auftretens eines Elements

from bisect import bisect_left


def binary_search(a, x):
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return -1


a = [1, 2, 3, 3, 3]
x = int(3)
res = binary_search(a, x)
if res == -1:
    print("Element not Found")
else:
    print("First occurrence of", x, "is at index", res)

Ausgabe:

First occurrence of 3 is at index 2

Finde den größten Wert kleiner als x

from bisect import bisect_left


def binary_search(a, x):
    i = bisect_left(a, x)
    if i:
        return i - 1
    else:
        return -1


# Driver code
a = [1, 2, 4, 4, 8]
x = int(7)
res = binary_search(a, x)
if res == -1:
    print("There is no value smaller than", x)
else:
    print("Largest value smaller than", x, " is at index", res)

Ausgabe:

Largest value smaller than 7 is at index 3

bisect.bisect_right() Überblick

Wird verwendet, um die äußerste rechte Einfügestelle einer Zahl x innerhalb einer sortierten Liste zu ermitteln. Wenn x bereits in der Liste vorhanden ist, dann wird das neue x an der äußersten rechten Position unter allen x in der Liste eingefügt.

Syntax

bisect_right(arr, x, lo=0, hi=len(a))

Parameter

Zurück

Es wird ein Einfügepunkt zurückgegeben, der das Array in zwei Hälften teilt: die erste mit allen Werten <= x und die zweite mit allen Werten > x.

Anwendungen von bisect_right()

Finden des letzten Vorkommens eines Elements

from bisect import bisect_right


def binary_search(a, x):
    i = bisect_right(a, x)
    if i != len(a) + 1 and a[i - 1] == x:
        return i - 1
    else:
        return -1


a = [1, 2, 4, 4]
x = int(4)
res = binary_search(a, x)
if res == -1:
    print(x, "is absent")
else:
    print("Last occurrence of", x, "is present at", res)

Ausgabe:

Last occurrence of 4 is present at 3