Comment puis-je implémenter efficacement une recherche binaire en Python pour vérifier l'existence d'un élément ?

Recherche binaire (recherche de halo) en Python

Python fournit des fonctions de bibliothèque pour implémenter la recherche binaire (également appelée recherche binaire), utilisée pour trouver éléments dans une liste triée ou un tuple. Cependant, ces fonctions renvoient toujours une position si l'élément n'est pas trouvé.

Pour résoudre ce problème et détecter uniquement si l'élément existe, une solution consiste à utiliser la fonction bisect.bisect_left() pour trouver la position d'insertion, puis à vérifier si l'élément à cette position est égal à l'élément cible. . Cependant, cela peut être fastidieux et nécessite également une vérification des limites lorsque le nombre est supérieur au plus grand nombre de la liste.

En raison de la consommation de mémoire, un dictionnaire est suggéré comme alternative dans la question. Cependant, cela peut nécessiter environ deux fois plus de mémoire.

Par conséquent, ce problème peut être résolu en implémentant une recherche binaire à l'aide d'un code personnalisé :

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):
    if hi is None: hi = len(a)
    pos = bisect_left(a, x, lo, hi)                 # find insertion position
    return pos if pos != hi and a[pos] == x else -1  # don't walk off the end

Cette fonction utilise la fonction bisect_left() pour trouver la position d'insertion, qui indique la position de l'élément cible s'il existe, ou indiquer une position hors de portée lorsqu'il n'est pas présent. Vous pouvez déterminer si l'élément cible existe en vérifiant si l'élément à cette position est égal à l'élément cible.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!