Cherchons des valeurs numériques par recherche linéaire / recherche de 2 minutes

Bonjour. Merci pour votre soutien m (_ _) m Cela fait presque trois semaines que j'ai commencé à publier le 23/09. C'est amusant en un rien de temps (rires).

Eh bien, cette fois, c'est une recherche. Commençons par une recherche linéaire. Vous n'avez pas besoin d'être prêt. 図1.PNG Juste comme ça, dans l'ordre à partir de la gauche, vérifiez si la valeur que vous recherchez correspond au déficit.

linear_search.py


def search(x,key):
    
    for i in range(len(x)):
        if x[i] == key:
            print(f"value is placed at x[{i}]")
            break
 #Terme final x[6] !=Pour clé, si x mentionné ci-dessus[i] ==Parce qu'il passe la clé
 #Entrez l'instruction if suivante telle quelle.
 #i == len(x)-Si c'est 1, c'est un échec.
        if i == len(x)-1:
            print("fail to serch")
            break


if __name__ == "__main__":
    x = [6,4,3,2,1,2,8]                      #Spécifiez un tableau
    key = int(input("enter search value: ")) #Entrez la valeur que vous souhaitez trouver
    search(x,key)

Ensuite, une recherche de 2 minutes. Les prérequis pour la recherche linéaire sont très différents. J'ai fait la différence en tant qu'image. 図2.PNG Dans le cas de la recherche linéaire, on compare des choses données à partir de la fin, La recherche de 2 minutes ne se déroule pas de cette façon. Alignez une fois. Veuillez noter que le départ est complètement différent. (? _ ?)(? _ ?)(?_?) Oui, je vais quand même passer à l'étape suivante. 図3.PNG Si vous recherchez ** 3 **, vous pouvez le trouver d'un seul coup en le comparant à la valeur médiane (rires) Mais que faire si vous recherchez une valeur inférieure à 3? 図4.PNG Que faire si la valeur que vous recherchez est ** 1 **? Si ce n'est pas la valeur médiane 2 de [1, 2, 2], c'est encore moins. Regardez simplement x [0] où le 1 est stocké. Si vous n'avez toujours pas la valeur que vous recherchez, vous cherchez quelque chose en premier lieu Il n'existera pas dans le tableau préparé. Mendoia Argo n'est pas bon à moins d'être organisé une fois, mais il semble assez célèbre. Cette fois, je l'ai écrit de manière récursive.

binary_search.py


def binary_search(x,left,right,key):
    cen = (left + right)//2
    if left > right:
        print(f"left is {left},right is {right}")
        print("faile to search")
        return None
    if x[cen] == key:
        return print(f"found at x[{cen}]")

    #Médiane x[cen]Est supérieur à la clé de recherche
    if x[cen] > key:
        print(f"left is {left},cen is {cen}")
        binary_search(x,left,cen-1,key)#cen-Un"-1"Est le miso!!!

    #Médiane x[cen]Est inférieur à la clé de recherche
    if x[cen] < key:
        print(f"cen is {cen},right is {right}")
        binary_search(x,cen+1,right,key)#cen+Un"+1"Est le miso!!!
    
if __name__ == "__main__":
    x =[1,2,2,3,4,6,8]
    
    binary_search(x,0,len(x)-1,1)

Résultat d'exécution.py


left is 0,cen is 3
left is 0,cen is 1
found at x[0]

Sélectionnez le côté gauche et rétrécissez-le progressivement. J'ai essayé de recréer l'image en augmentant la longueur du tableau. Cela peut être plus facile à comprendre (médiane rouge, ** si vous recherchez 7 **). 図5.PNG Et si vous ne recherchez pas ** 7 **? Veuillez faire attention au ** miso ** décrit ci-dessous.

miso.py


    #Médiane x[cen]Est supérieur à la clé de recherche
    if x[cen] > key:
        print(f"left is {left},cen is {cen}")
        binary_search(x,left,cen-1,key)#cen-Un"-1"Est le miso!!!

    #Médiane x[cen]Est inférieur à la clé de recherche
    if x[cen] < key:
        print(f"cen is {cen},right is {right}")
        binary_search(x,cen+1,right,key)#cen+Un"+1"Est le miso!!!

Juste au cas où, lorsque vous l'exécutez, vous verrez les commentaires suivants.

Résultat d'exécution.py


left is 5,right is 4 
faile to search

C'est vrai. gauche> droite est réalisé. Que voulez-vous dire?

Si vous recherchez ** 6 ** Entrez ** if x [cen]> key: ** dans la description.

Le résultat est ** binary_search (x, left, cen-1, key) **. À ce stade, gauche == droite, donc compte tenu de la formule ci-dessus gauche> droite, droite ??. C'est le mécanisme de l'inversion. Si vous venez si loin, vous pouvez dire qu'il n'y a rien, non? ??

Si quelqu'un peut l'écrire plus simplement Nous nous excusons pour la gêne occasionnée, mais merci de votre compréhension. m (_ _) m

Recommended Posts

Cherchons des valeurs numériques par recherche linéaire / recherche de 2 minutes
[Excel] Recherche de valeurs en double (caractères)