human
Algorithme de recherche binaire Je ne peux pas comprendre cela du tout. ELI5 ? Merci ! S'il vous plaît, expliquez-moi comme si j'avais cinq ans.
gpt
La recherche binaire est un moyen de déterminer si quelque chose que vous recherchez est un ensemble de données existant, l'ensemble de données doit absolument être en ordre ou la recherche binaire ne fonctionnera pas. Commençons par un tableau d'entiers : [ 0,1,2,3,4,5,6,7,8,9 ] Le tableau est dans l'ordre donc on peut faire la recherche , on voit aussi qu'il y a une taille fixe (10) d'une manière générale, nous appelons simplement ce nombre N. Je veux savoir si 6 est dans mon tableau et je veux savoir où il se trouve dans le tableau. Je pourrais simplement parcourir le tableau et voir si je le trouve , le problème avec ceci est que vous pourriez rechercher la dernière chose dans le tableau , vous prendriez 10 vérifications pour le trouver . Nous classons les opérations selon leur pire scénario, cette méthode s'appellerait une recherche d'ordre N car il faut au pire N vérifications pour trouver l'élément. Parce que votre tableau est ordonné, vous pouvez vérifier au milieu, si vous avez de la chance de trouver ce que vous cherchez, sinon vous pouvez éliminer la moitié du tableau parce que vous savez que tout ce qui est supérieur ou inférieur à ce que vous avez trouvé n'est plus pertinent . Commençons donc, utilisions le tableau ci-dessus et recherchions 9 . Nous commençons par trouver le nombre du milieu dans ce cas son 4 . Étant donné que le tableau a une taille paire, nous aurions pu dire que c'est 5, peu importe ce que vous choisissez, il vous suffit de le faire de la même manière à chaque fois. Donc nous avons le nombre 4, c'est plus petit que notre cible (6) donc nous n'avons pas encore découvert s'il est là, mais nous pouvons maintenant dire que tout de 0 à 4 peut être éliminé. Alors maintenant, notre tableau de recherche est [5,6,7,8,9] Maintenant, recommencez, choisissez l'élément au milieu (7) et examinez-le. 7 n'est pas ce que nous voulons donc n'a pas été fait. Cette fois 7 est plus grand que notre objectif de 7 , donc tout de 7 à 9 peut être ignoré , notre tableau de recherche est maintenant [ 5,6 ] . Alors reprenons , prenons le nombre du milieu ( 5 ) , ce n'est pas le nombre que nous voulons et il est plus petit que notre objectif , alors prenons tout le reste plus grand que lui dans le tableau , notre tableau de recherche est maintenant juste [ 6 ] [ 6 ] a seulement 1 élément donc c'est la dernière vérification que nous pouvons faire , vérifiez si la chose dans le tableau est 6 , c'est le cas ! Vous avez trouvé votre cible dans le tableau , renvoyez son emplacement dans le tableau ( 7 ) car il était à l' emplacement du tableau 7 . Si vous n'aviez pas trouvé la cible (vous êtes descendu à un élément et ce n'était pas ça), vous renvoyez -1 pour signifier qu'il n'y est pas. Il a donc fallu 5 étapes pour trouver notre cible au lieu de 7 comme cela aurait été le cas en parcourant simplement le tableau dans l'ordre. Comme je l'ai mentionné, cette méthode s'appelle une recherche d'ordre N où in est la taille du tableau. La recherche binaire a l'avantage de réduire la taille de notre recherche à chaque taille , c'est pourquoi nous disons que la recherche binaire est de commande log(n ) . Et c'est ainsi que fonctionne la recherche binaire.