Python Bisect - Recherche dichotomique

1. bisect.bisect_left() Présentation
2. Applications de bisect_left()
3. bisect.bisect_right() Présentation
4. Applications de bisect_right()

Dans cet article, nous verrons comment utiliser les modules intégrés Python pour effectuer une Recherche dichotomique. Le module bisect est basé sur la méthode de la bissection pour trouver les racines des fonctions. Il se compose de 6 fonctions: bisect(), bisect_left(), bisect_right(), insort(), insort_left(), insort_right() qui nous permet de trouver l’index d’un élément ou insérez un élément à la bonne position dans une liste. Cela permet également de garder la liste triée après chaque insertion. Mais pour qu’ils fonctionnent correctement, nous devons nous assurer que le tableau est déjà trié.

bisect.bisect_left() Présentation

Il est utilisé pour localiser le point d’insertion le plus à gauche d’un nombre x dans une liste triée. Si x est déjà présent dans la liste, alors le nouveau x sera inséré dans la position la plus à gauche parmi tous les x de la liste.

Syntaxe

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

Paramètres

Revenir

Il renvoie un point d’insertion qui partitionne le tableau en deux moitiés: la première avec toutes les valeurs inférieures à x et la seconde avec toutes les valeurs supérieures à x.

Applications de bisect_left()

Rechercher la première occurrence d’un élément

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)

Production:

First occurrence of 3 is at index 2

Trouvez la plus grande valeur inférieure à 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)

Production:

Largest value smaller than 7 is at index 3

bisect.bisect_right() Présentation

Il est utilisé pour renvoyer le point d’insertion le plus à droite d’un nombre x dans une liste triée. Si x est déjà présent dans la liste, alors le nouveau x sera inséré dans la position la plus à droite parmi tous les x de la liste.

Syntaxe

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

Paramètres

Revenir

Il renvoie un point d’insertion qui partitionne le tableau en deux moitiés: la première avec toutes les valeurs <= x et la seconde avec toutes les valeurs > x.

Applications de bisect_right()

Rechercher la dernière occurrence d’un élément

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)

Production:

Last occurrence of 4 is present at 3