recherche binaire Python

Une recherche binaire Python trouve la position d’un élément dans un tableau trié. Il divise une liste en deux. Si une valeur spécifiée est supérieure au nombre du milieu, la recherche se concentre sur la droite de la liste. Sinon, la recherche recherche le numéro à gauche de la liste.

Comment trouver la position d’un élément dans une liste ? Les recherches binaires vous soutiennent. En utilisant des recherches binaires, vous pouvez facilement trouver la position d’un élément dans un tableau trié.

Les ordinateurs sont bons pour rechercher dans les listes pour trouver un élément spécifique. Les règles que les ordinateurs utilisent pour trouver des éléments dans une liste sont appelées algorithmes de recherche. L’un des algorithmes Python les plus populaires est la recherche binaire.

Dans ce guide, nous allons discuter de ce que sont les recherches binaires et Comment ils travaillent. Nous allons parcourir un exemple de recherche binaire en Python afin que vous puissiez apprendre à en écrire une dans vos programmes. C’est parti !

Qu’est-ce qu’une recherche binaire Python ?

Une recherche binaire Python est un algorithme qui trouve la position d’un élément dans un tableau ordonné. Les recherches binaires divisent à plusieurs reprises une liste en deux moitiés. Ensuite, une recherche compare si une valeur est supérieure ou inférieure à la valeur médiane dans la liste.

Il existe deux façons d’effectuer une recherche binaire. Les deux approches définissent des pointeurs qui sont utilisés pour suivre les positions les plus hautes et les plus basses à un point particulier d’un tableau.

La première approche que vous pouvez utiliser est la méthode itérative. Dans cette approche, un ensemble d’instructions est répété pour déterminer la position d’un élément dans un tableau. En Python, nous utilisons une boucle while à cette fin.

L’autre approche est la méthode récursive. C’est là que vous écrivez une fonction qui s’appelle encore et encore jusqu’à ce qu’un élément dans une liste soit trouvé. La méthode récursive utilise l’approche diviser pour régner dont nous avons parlé plus tôt et répète le processus de recherche jusqu’à ce qu’un élément soit trouvé.

81 % des participants ont déclaré qu’ils se sentaient plus confiants quant à leurs perspectives d’emploi en technologie après avoir assisté à un bootcamp . Soyez jumelé à un bootcamp aujourd’hui.

Le diplômé moyen d’un bootcamp a passé moins de six mois en transition de carrière, du démarrage d’un bootcamp à la recherche de son premier emploi.

Avec tout ce discours sur la division et la conquête et la récursivité, il peut être facile de perdre de vue le fonctionnement exact d’une recherche binaire. Pour cette raison, nous allons passer directement à un exemple de fonctionnement de la recherche binaire. Considérez la liste suivante :

79142234

Nous allons chercher le nombre "22" dans notre liste.

Pour commencer, nous allons placer deux pointeurs dans nos listes. Un pointeur reflétera la valeur la plus élevée de la liste, et l’autre point reflétera la valeur la plus basse :

< /table>

Notre prochaine étape consiste à trouver l’élément du milieu dans le tableau, qui est 14. Si cette valeur est égale à la valeur que nous recherchons, alors cette valeur doit être renvoyée.

Dans ce cas, 14 n’est pas la même chose que 22. Notre programme doit donc effectuer une comparaison.

Nous allons comparer le nombre que nous recherchons avec l’élément central des éléments sur le côté droit de l’élément central actuel. Nous ne le ferons que si le nombre que nous recherchons est supérieur au nombre du milieu. Sinon, nous comparerons l’élément avec l’élément du milieu sur le côté gauche de l’élément du milieu actuel.

Le nombre 22 est supérieur à 14. Notre programme commence à comparer 22 à l’élément central sur le côté droit de notre élément central actuel (14). Dans ce cas, ce nombre est 22. Ceci est égal au nombre que nous recherchons.

Nous avons trouvé notre valeur médiane. Notre programme va maintenant renvoyer la position d’index de ce nombre. Dans ce cas, la position d’index de 22 est 3 (rappelez-vous, les listes sont indexées à partir de 0 !).

Comment implémenter un binaire Rechercher en Python

Let&rsq uo;s salissez-vous les mains avec du code Python. Nous allons explorer une implémentation Python d’une recherche binaire en utilisant les deux approches dont nous avons parlé précédemment : les méthodes itérative et récursive.

Recherche binaire itérative en Python

Nous‚Äô Je commencerai par la méthode itérative. C’est ici que nous parcourrons chaque élément de notre liste. Ensuite, nous trouverons la valeur médiane dans la liste. Nous continuerons à le faire jusqu’à ce que nous ayons trouvé la valeur que nous recherchons.

Fonction de recherche binaire

Commençons par définir une Fonction Python pour notre recherche binaire :

Notre fonction accepte deux paramètres : la liste dans laquelle on veut chercher, et le nombre que l’on veut trouver dans notre liste.

Nous avons ensuite déclaré deux variables Python qui stockent les valeurs par défaut pour les valeurs les plus basses et les plus élevées de la liste. < em>low est défini sur 0, qui est la valeur d’index de départ dans la liste. high est défini sur la longueur de la liste m inus one (car les listes sont indexées à partir de zéro).

Notre prochaine étape consistait à déclarer une Python while loop. Cette boucle s’exécute alors que l’élément le plus bas est inférieur ou égal au nombre le plus élevé. Cela signifie que notre boucle ne fonctionnera que si notre numéro n’a pas encore été trouvé.

Ensuite, nous calculons le nombre du milieu. Nous le faisons en soustrayant la valeur la plus faible de la valeur la plus élevée. Nous calculons ensuite le modulo (reste) de ce nombre lorsqu’il est divisé par 2. Ensuite, nous ajoutons le modulo à la valeur du nombre le plus bas.

Si le nombre du milieu dans notre liste est le même que le nombre nous voulons trouver, nous retournons la position de ce nombre.

Nous définissons notre nouveau "bas‚" nombre doit être égal à un supérieur à la position médiane. Cela se produit si le nombre du milieu est inférieur au nombre que nous voulons trouver. Cela déplace notre recherche vers le côté gauche de notre liste, comme nous l’avons fait dans notre exemple visuel plus tôt.

Sinon, nous définissons notre nombre "élevé" pour qu’il soit égal à un de moins que la position médiane. Cela déplace notre recherche vers le côté droit de notre liste.

" Carrière Karma est entrée dans ma vie au moment o√π j’en avais le plus besoin et m’a rapidement aidé à participer à un bootcamp. Deux mois après avoir obtenu mon diplôme, j’ai trouvé l’emploi de mes rêves qui correspondait à mes valeurs et à mes objectifs dans la vie !"

Venus, ingénieur logiciel chez Rockbot

Ceci est répété jusqu’à ce que bas soit égal ou inférieur à haut. Si notre valeur n’est pas trouvée, nous renvoyons -1. Nous expliquerons pourquoi dans une minute.

Exécutez la recherche

Ajoutez le code suivant au bas de votre programme, en dehors de la fonction findValue :

Nous avons commencé par déclarer la liste d’éléments à travers lesquels nous voulons rechercher. Ensuite, nous avons spécifié le nombre que nous voulons trouver, qui est 22.

Ensuite, nous appelons notre fonction findValue() a et passez-y la liste.

Voici d’o√π vient le -1 plus tôt. Si le nombre renvoyé par notre fonction est -1, cela signifie que notre élément n’a pas été trouvé dans la liste. Les programmeurs utilisent souvent -1 dans des situations comme celle-ci car notre fonction de recherche ne peut pas renvoyer un nombre négatif.

Sinon, notre programme affiche un message nous indiquant la position d’index de cette valeur.

Notre code renvoie :

Maintenant, nous savons que le nombre 22 apparaaît à la position d’index 3.

Recherche binaire récursive en Python

Nous pouvons également utiliser la récursivité pour effectuer une recherche binaire. C’est là que nous allons définir une fonction qui continue de s’appeler jusqu’à ce qu’une condition ‚Äì notre numéro étant trouvé ‚Äì est remplie.

Définir une fonction récursive

Comme dans notre dernier exemple, nous allons commencer par écrire une fonction qui effectue notre recherche binaire :

Notre code est quelque peu similaire à notre dernier exemple.

Nous commençons par vérifier si la valeur la plus élevée est supérieure ou égale à faible. Si c’est le cas, notre programme renverra -1. Sinon, il commencera à effectuer une recherche binaire.

Nous calculons le nombre du milieu en utilisant la même approche que dans le dernier exemple. Tout d’abord, nous soustrayons la valeur la plus faible de la valeur la plus élevée. Ensuite, nous calculons le modulo (reste) de cette valeur lorsqu’il est divisé par 2. Enfin, nous ajoutons le nombre le plus bas.

Nous avons ensuite écrit une instruction if qui décide comment notre recherche binaire doit se poursuivre :

  • Si le nombre du milieu est égal à celui que nous recherchons, la position de ce nombre est renvoyée.
  • Si le nombre du milieu est inférieur à celui que nous recherchons, notre fonction findValue() est à nouveau appelée. Cette fois, la valeur de low est définie pour être égale à un supérieur à notre valeur médiane.
  • Si le nombre médian est supérieur à celui que nous recherchons, le < La fonction em>findValue() est appelée. La valeur de "élevée" sera égal à un de moins que la valeur médiane.

Écrire le programme principal

Il ne nous reste plus qu’à écrire notre programme principal :

Notre programme principal est le même que notre exemple précédent à une différence près. Nous passons deux nouveaux paramètres à notre fonction findValue() : bas et haut.

Nous devons le faire car notre algorithme est récursif et nous ne pouvons pas affecter ces valeurs à notre fonction. Si nous attribuions les valeurs à notre fonction, ces valeurs seraient réinitialisées à chaque exécution de notre fonction, ce qui casser notre algorithme de recherche.

Notre code renvoie :

Nous avons reçu le même résultat que précédemment. Dans cet exemple, nous avons utilisé un programme récursif au lieu d’un programme itératif pour effectuer notre recherche binaire.

Quand devriez-vous utiliser une recherche binaire Python ?

Une recherche binaire est une moyen efficace de rechercher dans une liste de nombres. Cette recherche est plus efficace qu’une recherche linéaire. En effet, la méthode binaire réduit votre recherche de moitié dès que vous trouvez le milieu d’une liste triée.

Il est important de noter qu’une liste doit être ordonnée numériquement avant de pouvoir être recherchée en utilisant une recherche binaire. Avant d’effectuer une recherche binaire, assurez-vous que vos nombres sont triés par ordre croissant.

Recherche binaire dans Python Complexity Breakdown

Quelle est la complexité d’une recherche binaire ? C’est une bonne question.

L’algorithme de recherche binaire a une complexité de meilleur cas de O(1). Cela se produit lorsque la première comparaison est égale à l’élément que vous recherchez.

La complexité moyenne et pire des cas pour une recherche binaire est O(log n). Cela signifie que le temps nécessaire pour effectuer une recherche augmente de manière logarithmique en fonction du nombre d’éléments à rechercher dans une liste.

Conclusion

Les recherches binaires sont un moyen efficace pour trouver la position d’index d’une valeur dans une liste.

Chaque fois qu’une recherche binaire est exécutée, la recherche divisera la liste en deux parties. La recherche se concentre sur le côté de la liste le plus proche du numéro que vous recherchez.

Pour chaque fois que la recherche est exécutée, le nombre de numéros à travers lesquels le programme doit rechercher est divisé par deux.

Pour en savoir plus sur Python, lisez notre Guide d’apprentissage de Python.

Faible


√âlevé
79142234