Comment puis-je vérifier efficacement la présence d'un élément dans une liste triée à l'aide de la recherche binaire en Python ?

Recherche binaire (Bisection) en Python avec vérification explicite de la présence d'éléments

Le module Python bisect fournit des fonctions permettant d'effectuer une recherche binaire, telle que bisect_left et bisect_right. Cependant, ces fonctions renvoient une position même si l'élément recherché n'est pas présent dans la liste. Pour les cas où seule la présence ou l'absence d'un élément est souhaitée, une vérification plus explicite est requise.

Une approche consiste à utiliser bisect_left et à vérifier si l'élément à la position renvoyée correspond à la cible. Cependant, cette méthode introduit une complexité supplémentaire, telle que la vérification des limites dans les cas où la cible est plus grande que le plus grand élément de la liste.

Une solution plus simple et plus directe consiste à implémenter une fonction de recherche binaire personnalisée qui vérifie explicitement pour la présence de l'élément avant de renvoyer le résultat. Voici un exemple :

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 prend une liste triée a, une valeur cible x et des limites inférieure et supérieure facultatives pour la recherche. Il utilise bisect_left pour trouver le point d'insertion de x, puis vérifie si l'élément à cette position correspond à la cible. Si une correspondance est trouvée, la fonction renvoie la position ; sinon, il renvoie -1 pour indiquer l'absence de l'élément.

En incorporant cette vérification explicite, vous pouvez déterminer efficacement la présence ou l'absence d'un élément dans une liste triée sans introduire de surcharge ou de limitations inutiles.

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!