Python Bisect - Recherche dichotomique
-
bisect.bisect_left()
Présentation -
Applications de
bisect_left()
-
bisect.bisect_right()
Présentation -
Applications de
bisect_right()
![Python Bisect - Recherche dichotomique](/img/Python/feature-image---python-bisect.webp)
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
arr |
La liste d’entrée |
x |
L’élément dont nous localisons le point d’insertion. |
lo |
Il permet de spécifier l’index de départ d’un sous-ensemble d’une liste. La valeur par défaut est 0 . |
hi |
Il permet de spécifier l’index de fin d’un sous-ensemble d’une liste. La valeur par défaut est len(arr) . |
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
arr |
La liste d’entrée |
x |
L’élément dont nous localisons le point d’insertion. |
lo |
Il permet de spécifier l’index de départ d’un sous-ensemble d’une liste. La valeur par défaut est 0 . |
hi |
Il permet de spécifier l’index de fin d’un sous-ensemble d’une liste. La valeur par défaut est len(arr) . |
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
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn