Salut et bienvenue dans ce nouvel épisode du podcast de Code Garage, je m'appelle
Nicolas Brandon-Bernard et aujourd'hui on va parler de la recherche binaire.
Alors la recherche binaire c'est un algorithme qui est utilisé pour trouver un élément
dans une liste triée.
C'est très important puisque c'est un algorithme qui est très efficace mais il ne fonctionne
qu'avec une liste triée.
En fait, il repose sur le principe de division de la liste et on va diviser notre liste
en deux parties à chaque étape, à chaque nouvelle étape on va découper notre liste
en deux et ce qui va réduire le nombre d'éléments à examiner à chaque fois et c'est pour ça
que c'est un algo qui est très efficace.
En fait, l'idée centrale c'est d'exploiter le fait comme je disais que la liste est
triée donc au lieu de parcourir les éléments un par un comme on ferait dans une recherche
linéaire classique, on va commencer par examiner l'élément du milieu de la liste.
Donc voilà comment est-ce que ça se passe.
D'abord, on va regarder l'élément du milieu.
Si jamais ça correspond exactement à l'élément qu'on cherche, admettons qu'on cherche le
nombre 11.
On va regarder si oui ou non notre élément du milieu de la liste est égal au niveau
11.
Si c'est le cas, évidemment la recherche s'arrête.
Si jamais l'élément qu'on recherche, admettons qu'on est actuellement à l'élément 22 et
que nous on cherche l'élément 11, il est plus petit, on va considérer que la moitié
est inférieure de la liste et on va laisser complètement de côté la moitié supérieure.
A l'inverse, si jamais l'élément recherché est plus grand, on va enlever la partie inférieure
et garder que la partie supérieure.
En fait, ce processus, on va le répéter de manière récurcive ou iterative d'ailleurs
on peut faire les deux jusqu'à trouver l'élément où que la liste soit vide.
Si la liste est vide, ça veut tout simplement dire que notre élément n'existe pas.
Donc on va renvoyer un index moins un ou peu importe et s'il existe, on va renvoyer
l'index de la position de cet élément dans la liste.
Ce qui est hyper intéressant, c'est que la recherche binaire, elle a une complexité
qu'on appelle en grand haut log de n.
Si jamais vous n'êtes pas hyper familier avec le concept de complexité algorithmique,
on a un article qui sort très prochainement sur code garage.
Si jamais il est déjà sorti quand vous écoutez ce podcast, je vous mettrai le lien
dans les notes de cet épisode.
Et donc une complexité en logarithm de n, ça veut dire que le nombre d'opérations
qui va être nécessaire pour trouver un élément, un autre élément, il va croître, mais il
va croître logarithmiquement en fonction de la taille de la liste.
Alors ça rend la recherche vraiment beaucoup plus rapide qu'une recherche linéaire.
Une recherche linéaire, sa complexité, c'est n.
Donc c'est le nombre d'éléments de la liste.
Donc admettons qu'on ait un million d'éléments dans notre liste.
Et bien la complexité logathmiques, c'est un million.
Tandis que log, logarithm de un million, le logarithm de un million, c'est 20.
Donc on se rend un petit peu mieux compte de quel monde sépare ces deux méthodes.
Simplement, il y en a une, la recherche linéaire qu'on peut faire, même si la liste n'est pas triée.
Mais par contre, dès que la liste est triée, on va vraiment profiter de cette puissance
de l'algorithme de la recherche binaire.
Donc je rappelle un petit peu, imaginons que vous avez une liste avec un million d'éléments.
Et bien vous allez prendre l'élément numéro 500 000 qui est pile au milieu de la liste.
Et puis vous allez regarder sa valeur.
Si sa valeur est trop grande, on va prendre la partie inférieure.
On va couper en deux exactement à cet endroit-là et on va reprendre un élément au milieu de la partie
qu'on vient de récupérer, la partie inférieure.
A l'inverse, on va récupérer la partie supérieure et récupérer l'élément du milieu.
Et à chaque fois, on reprend le milieu, du milieu, du milieu, du milieu, des endroits qu'on coupe dans la liste.
La liste devient de plus en plus petite et donc évidemment notre nombre d'intérations grandit.
Mais grandit de manière logarithmique.
Alors quand est-ce qu'on utilise la recherche binaire ?
Comme je l'ai dit, évidemment c'est dès qu'on peut, en tout cas dès qu'on peut parce que la liste est triée.
Mais on l'utilise beaucoup en base de données, notamment pour justement le concept d'index.
Si jamais le concept d'index en base de données vous parle pas trop,
eh bien je vous mets en lien directement un podcast où je vous explique tout ça.
Mais ça peut être dans un système de fichiers.
Et même dans une intelligence artificielle, quand on a un nombre de résultats qui sont triés par score,
eh bien quand on va vouloir récupérer des résultats à partir d'un certain score,
on va pouvoir faire une recherche binaire aussi.
Donc c'est vraiment un algorithme qui est fondamental en programmation.
Et pourtant, vous voyez, en fait il est très très simple.
Et même si vous vouliez l'implémenter de votre côté, vous verrez que c'est très très simple.
Evidemment il y a des centaines et des milliers, des centaines de milliers d'exemples sur le net.
Mais ça peut être intéressant comme exercice.
Nous allons d'essayer de l'implémenter soi-même.
Vous verrez que c'est vraiment très très facile.
J'espère que vous aurez appris quelque chose.
Peut-être que beaucoup d'entre vous connaissaient déjà évidemment la recherche binaire.
Mais bon, si jamais vous le connaissiez déjà, eh bien n'hésitez pas à partager cet épisode,
notamment à des développeurs et développeuses junior qui peut-être ne connaissent pas ce concept.
Et si vous ne connaissiez pas et que vous avez appris quelque chose,
eh bien pensez à laisser cinq étoiles sur Spotify, Apple Podcast, Deezer, peu importe.
Là vous écoutez ce podcast, ça aide pour le référencement et puis ça nous soutient tout simplement dans notre travail.
Moi je vous retrouve la semaine prochaine pour un prochain épisode du podcast.
Mais avant de vous laisser, je voulais vous annoncer qu'on vient de sortir
une des premières vraies formations en ligne pour apprendre le Kobol.
Le Kobol c'est un langage des années 60 mais qui fait encore tourner 70% des transactions financières dans le pays.
Donc c'est vraiment quelque chose qui est hyper important et il y a une vraie pénurie de développeurs et développeuses Kobol.
Donc il y a une vraie opportunité aussi pour vous et c'est souvent un petit peu compliqué de l'apprendre
parce que non pas parce du langage mais parce que la documentation n'est pas super bien faite, pas très accessible.
On vous a fait un cours complet de 1 heure où vous pouvez apprendre le Kobol de A à Z.
En tout cas avoir toutes les bases en simplement 1 heure avec tout ce qu'il faut, tout ce qui est installé etc.
Donc n'hésitez pas, je vous mets le lien directement dans les notes de l'épisode.
Venez faire un tour évidemment sur code-garch.com pour retrouver tous nos articles de blog, nos épisodes de podcast
et puis comme je l'ai dit tous nos cours complet.
Voilà et moi je vous retrouve sur la plateforme ou la semaine prochaine pour un prochain épisode du podcast. Salut !