Cette fonction de recherche binaire Python trouve-t-elle l'élément ?

Recherche binaire (bissection) en Python

Déterminer si un élément est présent dans une liste triée ou un tuple est une tâche courante en programmation. Alors que Python fournit le module bisect pour la recherche binaire, ses fonctions bisect_left et bisect_right renvoient une position même si l'élément n'est pas trouvé. Pour répondre à ce besoin, une implémentation Python de recherche binaire qui renvoie explicitement une valeur booléenne est introduite.

Solution proposée

La fonction binaire_search prend une liste triée 'a' , un élément « x » à rechercher et des positions de début et de fin facultatives « lo » et « hi » pour la plage de recherche. Il utilise la fonction bisect_left du module bisect pour localiser le point d'insertion 'pos' pour 'x' dans la liste 'a'.

Si 'pos' est inférieur à 'hi' et l'élément à 'pos ' est égal à 'x', alors 'x' est trouvé et 'pos' est renvoyé comme index de son emplacement dans la liste. Cependant, si « pos » atteint la fin de la liste (c'est-à-dire que « pos » est égal à « hi »), « x » n'est pas trouvé et la fonction renvoie -1.

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

Exemple d'utilisation

Par exemple, étant donné une liste triée 'a' et un élément 'x' à rechercher, la fonction binaire_search peut être utilisée comme suit :

result = binary_search(a, x)

if result == -1:
    print("Element not found")
else:
    print("Element found at index", result)

Cette fonction Python concise fournit un moyen pratique d'effectuer une recherche binaire pour vérifier l'existence d'éléments dans des listes triées tout en conservant la simplicité et l'efficacité de la recherche binaire.

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!