Les Algorithmes de recherches(binary search)

Les algorithmes de recherche consiste à efficacement rechercher un élement dans une structure de données (une liste ou un vecteur/array/tableau etc..), comme vous pouvez voir sur l'image associée à ce post (image au dessus), un algorithme prend des données entrée d'un probleme et restitut un résultat qui consiste à la resolution du probleme qu'il voulait resoudre, dans le cas des algorithmes de recherche, il s'agit de dire si un élement existe dans une structure de données et dans le cas échant, retourner sa position ou son index dans la structure. l'efficacité d'un algorithme se juge en utilsant la notation grand O ou Big O notation en anglais O(n), n est le nombre de parametres en entrée, et on juge l'efficacité de l'algorithme en voyant comment il se comporte quand le nombre de parametre en entrée accroit, on parlera d'une complexité de O(1) donc constant dans le cas ou en augmentant les parametres en entrée, on a exactement le meme resultat sans effectuer beaucoup d'operation, de la meme manière on retrouve des complexité en O(n) donc lineaire, en O(n2), O(log(n) ) etc.. les 3 principaux algo de recherches sont:

>Recherche Lineaire (Linear search)

>Recherche Binaire (Binary Search)

>Recherche par interpolation ( Interpolation Search)

===> Recherche linéaire

Dans ce type de recherche, on parcourt la liste (structure de donnée) à la recherche d'un element specifique qu'on veut trouver, la liste n'est pas ordonée, quand on retrouve l'élement recherché, on arrete la recherche, si on a l'element recherché au fond de la liste, alors on devra parcourir toute la liste, donc la complexité ici comme vous pouvez l'immaginé est lineaire ou O(n) (en image vous avez une implementation simple d'une recherche lineaire en javascript)

==> Recherche Binaire

Le prerequis dans cet algorithme est qu'on doit avoir une liste ordonnée en entrée (sorted list en anglais) et dans ce cas on a une efficacité de l'ordre de O(log(n)), donc plus efficace qu'une recherche linéaire en terme de nombres d'operations à faire. L'algorithme consiste simplement à diviser la liste en deux parties(on divise toujours pour mieux reigner non?), puis on reguarde si la valeur recherchée est à droite ou à gauche, si c'est à droite on se concentre seulement sur les elements à droites, puis on redivise la liste des elements à droite ainsi de suite jusqu'à on retrouve l'element recherché, en faisant ainsi on va faire moin d'operation comparativement à une recherche lineaire, mais ici la liste doit etre dejà ordonée pour etre efficace, par contre la recherche lineaire est efficace pour une liste non ordonée (en image un exemple en javascript).

==>Interpolation Search

Dans une recherche par interpolation, on utilise la valeur recherchée pour estimer sa position dans la structure et non diviser par deux comme le fait la recherche binaire, par exemple si la valeur recherchée est plus proche du dernier element de la liste, pourquoi diviser la liste par deux et commencer la recherche au milieux comme le fait le binaru search? ici la complexité est en terme de log(log(n) ) donc plus reduit (en image une implementation de search interpolation en javascript).

la suite dans les prochains post

Abbonnez vous dans ce blog pour continuer à etre alerté quand il y a des nouveaux post, il suffit de soit vous inscrire à la newsletter, soit de vous abbonnez et vous puvez donc poser vos questions qui seront repondu.

Bon Coding

---

---

Share

Comments (0)

Leave A Comment

Your Name:
Comment: