Comment utiliser Python pour implémenter la recherche binaire

Tout d'abord, créez une fonction nommée binaire_search : passez deux paramètres, la liste des éléments et la valeur que vous souhaitez rechercher.

def binary_search(_list, value):

Ensuite, définissez les variables requises à l'intérieur de la fonction. La clé de la dichotomie est de rechercher du milieu de la liste vers les deux côtés (l'expression n'est peut-être pas rigoureuse, mais c'est ce qu'elle signifie), donc pour le bien de intuition, définir gauche, droite, milieu Trois variables représentent : l'index de départ, l'index de fin et l'index du milieu de la liste.

    left = 0   # 列表的起始索引
    right = len(_list)   # 列表的结束索引
    mid = int((left + right)/2)  # 采用此方法，通过四舍五入刚好可以定位到列表的中间位置

L'étape suivante consiste à implémenter la partie clé de la recherche binaire. Définissez d'abord une boucle while afin que la recherche puisse se dérouler sans problème. Si les instructions de branche sont imbriquées dans la fonction while pour implémenter le jugement conditionnel, il existe trois situations :

1. _list[mid] == value : La valeur intermédiaire se trouve être la valeur que nous devons trouver, il suffit donc de renvoyer directement l'index correspondant.

2. _list[mid] > value : La valeur à trouver se trouve sur le côté gauche de mid. Mettez à jour la valeur de right à mid pour affiner la plage de recherche.

3._list[mid]

Enfin, mettez à jour la valeur de mid pour lancer le prochain cycle de recherche. En même temps, utilisez l'instruction while-else pour juger de la situation où elle n'est pas trouvée et donnez une valeur de retour.

    while left < right:
        if _list[mid] == value:
            return mid
        elif _list[mid] > value:
            right = mid
        else:
            left = mid
        mid = int((right + left)/2)
    else:
        return -1

Enfin, le code complet et les performances d'exécution des tests sont les suivants :

""" a demo realize binary search"""
 
 
def binary_search(_list, value):
    left = 0   # 列表的起始索引
    right = len(_list)   # 列表的结束索引
    mid = int((left + right)/2)  # 采用此方法，通过四舍五入刚好可以定位到列表的中间位置
    while left < right:
        if _list[mid] == value:
            return mid
        elif _list[mid] > value:
            right = mid
        else:
            left = mid
        mid = int((right + left)/2)
    else:
        return -1
 
 
index = "the index of value in the list: {}"
print(index.format(binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9], 1)))

Résultats d'exécution :

Lorsqu'il n'y a aucune valeur à trouver :

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!