Python Bisect - Ricerca binaria

In questo articolo vedremo come utilizzare i moduli integrati di Python per eseguire la ricerca binaria. Il modulo bisect si basa sul metodo di bisezione per trovare le radici delle funzioni. Consiste di 6 funzioni: bisect(), bisect_left(), bisect_right(), insort(), insort_left(), insort_right() che ci permette di trovare l’indice di un elemento o inserire l’elemento nella giusta posizione in una lista. Aiuta anche a mantenere la lista ordinata dopo ogni inserimento. Ma affinché funzionino correttamente, dobbiamo assicurarci che l’array sia già ordinato.

bisect.bisect_left() Panoramica

Viene utilizzato per individuare il punto di inserimento più a sinistra di un numero x all’interno di una lista ordinato. Se x è già presente nell’lista, la nuova x verrà inserita nella posizione più a sinistra tra tutte le x nell’lista.

Sintassi

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

Parametri

Ritorno

Restituisce un punto di inserimento che divide l’array in due metà: la prima con tutti i valori inferiori a x e la seconda con tutti i valori maggiori di x.

Applicazioni di bisect_left()

Trova la prima occorrenza di un elemento

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)

Produzione:

First occurrence of 3 is at index 2

Trova il valore più grande minore di 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)

Produzione:

Largest value smaller than 7 is at index 3

bisect.bisect_right() Panoramica

Viene utilizzato per restituire il punto di inserimento più a destra di un numero x all’interno di una lista ordinato. Se x è già presente nell’lista, la nuova x verrà inserita nella posizione più a destra tra tutte le x nell’lista.

Sintassi

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

Parametri

Ritorno

Restituisce un punto di inserimento che divide l’array in due metà: la prima con tutti i valori <= x e la seconda con tutti i valori> x.

Applicazioni di bisect_right()

Trova l’ultima occorrenza di un elemento

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)

Produzione:

Last occurrence of 4 is present at 3