Designed by Vince El Roubio !
177 en ligne   Boutique | Sites | Bar | Forum | PhpBB | Actu | Glossaire | Codes | Tips | Liens | Livres | Lettre  


 Recherche

 NewsLetter





   

La recherche dichotomique

Technique de programmation





AllJinx
La recherche séquentielle est efficace mais montre très vite ses limites dans les tables de valeurs à fortes dimensions. D'où la nécessité de connaître cette technique légèrement plus subtile.

Définition et utilité

La recherche dichotomique est une technique algorythmique applicable dans n'importe quel langage de programmation (du moment que l'on peut faire des boucles bien sur). Elle est utilisable UNIQUEMENT dans des tables de données ordonnées !!! (Ce qui est souvent le cas). Nous pouvons lui trouver une utilité lorsque les données d'un tableau commencent à se faire nombreuses et donc leur parcours laborieux pour les vieille bécanes et autres mobilettes.





Principe

Le principe est assez simple mais assez difficile à expliquer.
Prenons par exemple un tableau (Array) JavaScript, que nous nommerons de façon originale leTablo. Considérons que la valeur recherchée est stockée dans la variable leCherche. (Essayez de suivre avec l'illustration et l'exemple ce sera plus clair :) Considérons que celui-ci est rempli avec des nombres aléatoires classés par ordre croissant.
Nous stockons dans deux variables, l'index du premier élement de notre tableau (en général 0 ou 1) puis le dernier. Nous appellerons ces variables tout à fait au hazard Min et Max. Ces variables vont en quelque sorte nous servir de délimiteur du tableau : ce sont des bornes qui délimiterons la partie du tableau dans laquelle la valeur doit se trouver (sous réserve qu'elle existe bien sur).

Min=1; Max=leTablo.length;

Nous stockons ensuite l'index du milieu de notre tableau retourné. Toujours originaux, nous la nommerons Mil.
Mil=parseInt((Max+Min)/2);

Il suffit après de comparer la valeur du contenu de leTablo situé à l'index Mil, à leCherche.

if(leTablo[Mil]>leCherche)

Si la condition est juste, celà signifie que si la valeur existe dans le tableau, elle ne se situe pas dans la partie située entre sa moitié et sa fin. Nous n'avons donc plus besoin de ce morceau. Nous allons donc redéfinir notre délimiteur de fin (Max) pour qu'il vienne se placer au niveau du Milieu du tableau (fournit par Mil).

Max=Mil

Sinon, dans le cas inverse, c'est notre délimiteur de début que devra se déplacer.

Min=Mil

Le tout devant être répété dans une boucle qui se terminera quand Mil et Min seront égaux.

while(Mil!=Min){

A la sortie de la boucle, il en vous restera plus qu'à tester si la valeur située à l'index Min (= Mil) de leTablo correspond à leCherche. Si c'est le cas, c'est que la valeur à été trouvée. Sinon, cela signifie que la valeur n'a pas été trouvée et que la boucle s'est arrêtée car Mil et Min se sont retrouvés.





Graphiquement ca donne quoi ?









Exemple de script

L'exemple ci-dessous crée un tableau avec les lettres de l'alphabet pour valeur. Il suffit ensuite de rentrer une lettre dans le champs et d'appuyer sur le bouton pour lancer la fonction qui heberge la recherche dichotomique. Pensez que cette technique trouve aussi bien son salut dans les éléments SELECT et les tableaux à X dimensions.


dichotomie.htm 
<script language="JavaScript">

// Création du tableau
var leTablo= new Array();
// Remplissage du tableau
// ici avec les lettres de l'alphabet
// mais ça pourrait être n'importe quelles chaînes
for(i=1;i<27;i++) leTablo[i]=String.fromCharCode(64+i);


function Cherche(){

   var leCherche=document.neb.champs.value.toUpperCase();
   var Min=1;
   var Max=leTablo.length;
   var Mil=parseInt((Max+Min)/2);// On force en nombre entier
   
   while(Mil!=Min){
      if(leTablo[Mil]>leCherche)
         Max=Mil
      else
         Min=Mil;
      Mil=parseInt((Max+Min)/2)
   }
   
   if(leTablo[Min]==leCherche)
      window.alert("J'ai trouvé le "+leCherche+" à l'index "+Min+ " !!!")
   else
      window.alert("Cette valeur n'existe pas dans le tableau !");

   return false // pour ne pas soumettre le form
}

</script>

<form name="neb" onSubmit="return Cherche()">
   <input name="champs" id="champs" size="5">
   <input type="Submit" value="Cherche">
</form> 


Pour pouvoir écrire dans ce forum, identifiez-vous !

  v1.3p © ASP-PHP.net 2002  

AllJinx le 16/12/2002 (29 253 hits)
Didier 11 logiciels Microsoft GRATUITS dont Visual Studio 2008 Pro,
SQL Server 2005, Expression Studio, Windows Server 2003, Office project Pro, etc... !!!
Au fil des news  
Magazines - Le n°108 de Programmez est disponible
Adobe - Téléchargez gratuitement le dossier spécial Adobe
Magazines - Le N°107 de Programmez est disponible.
Créer une Feature d'administration sous SharePoint - Comment créer un composant d'administration
Dans les précédents articles, nous avons évoqué la création de pages personnalisées dans ...
PHP - Afficher une date : multilangage et relative
Agenda - Inscrivez-vous au WygDay [Wygwam] le 22/5 à Lille
Sync Framework - Introduction au MS Sync Framework - Installation
Microsoft, lors du Keynote du TechEd Europe 2007, a annoncé la mise à disposition d'un nouveau ...
Reporting Services et SharePoint - Utiliser SharePoint comme source de données
Dans un précédent article, nous avons pu apprendre comment créer un rapport utilisant une source de ...
JavaScript - Affiche un calendrier sous une zone de saisie
Adobe - Adobe lance la version bêta publique de Photoshop
Microsoft Expression Web - Premier contact
Je suis revenu des Techday's 2008 avec une idée en tête. Je voulais savoir comme travailler avec ...
PHP & MySQLi - de Hello / Sector One
Hello de Sector One propose un article avec PHP et MySQLi, la nouvelle extension de MySQL
VBScript - Zip de fichiers automatique et efface la source
Dreamweaver CS3 + Php + Mysql - Trucs et Astuces - Part 4 -
Pour changer, deux nouvelles astuces pour vous . Alternate Colors. Inscription et envoi de mail
Magazines - Le N°106 de Programmez est disponible.
Divers - Zone Webmasters
PHP5 - Classe de connexion à MySQL
Agenda - 20/03 : Boostez vos applis PHP-Windows Server 2008
Créer un thème graphique pour WSS V3 - Comment créer un thème graphique pour WSS V3
Nous avons vu dans un précédent article comment créer une master page. Il peut parfois être ...
Les plans de maintenance et SQL Server 2000 - Installer un plan de maintenance sous SQL Server
Dans le cadre de la gestion d'instances SQL Server 2000 hébergeant SharePoint, il est intéressant ...
PHP - PHP et MYSQL - MySQLi - PDO
Jeux de l'été (et de 4) - Un petit jeu de Mastermind
C'est reparti pour un tour... Il y avait longtemps que je n'étais pas venu vous proposer un petit ...
Migration WSS avec un Site Template spécifique - Migration WSS avec un Site Template spécifique
Les précédents articles nous ont permis de voir les différents modes de migration de WSS V2 vers ...
DataBase Upgrade de WSS V2 vers WSS V3 - Upgrade de WSS V2 vers WSS V3 par la DataBase
Parmi les trois modes de migration de Windows SharePoint Services V2 vers WSS V3, nous avons vu les ...
Création de module DotNetNuke en C# - Source : Jerome Fortias sap-integration.net
Je vous propose un nouvel article consacré au développement de modules pour DotNetNuke en C#. Il ...
ASP-PHP.net - On sera aux MS TechDays 2008 ! et vous ?
Créer son modèle de rapports SSRS - Créer son modèle de rapports Reporting Services
Après la création du modèle de style pour Reporting Services, il est souhaitable aussi d'avoir un ...
PHP - publipostage sur rtf préformaté avec mysql
Créer son style de rapports SSRS - Créer son style de rapports Reporting Services
Lorsqu'on travaille avec Reporting Services pour développer ses rapports, on veut très souvent ...
.NET - C#2 et ASP.NET 2.0 - Développez un projet de A à Z
SharePoint - MOSS 2007 - De l'intégration au développement
PHP - PHP 5 MySQL 5 AJAX
Découverte de Visual Studio 2008 -
Microsoft a annoncé, lors du TechEd'07 organisé à Barcelone, la mise à disposition de la release de ...
Adobe - Photoshop Elements 6 Version MAC
Adobe - Adobe sur Intergraphic 2008
Reporting Services et données XML - Utiliser des données XML dans Reporting Services
Une demande récente que j'ai reçue : Comment utiliser des données provenant d'un flux XML dans ...
Dreamweaver CS3 + XML + Ajax - Création d'une région détail
Dans cet article, je vais vous montrer comment utiliser la technique région détail, avec Spry
PHP - Jolie arborescence dynamique
Magazines - Le N°104 de Programmez est disponible
PHP - PhPBB 3.0.0 !!!
Tutorial : HTML | Scripting | ASP-PHP | ASP.net | SQL Server | XML
Sharepoint | XAML | Pocket | Dreamweaver | VML | Divers
  Scripts : Scripting | ASP-PHP | ASP.net | Divers
  Boutique | Annuaire | Bannières | Météo | Tribune | Partenariats
v3 © Didier 2003   
 

Corpo Sciences de Reims Partitions gratuites Carte, météo, annonces
 MVP El Roubio Codes Sources CodePPC ASP-magazine DotNet Project Groupes Utilisateurs Microsoft The Inquirer FR TechNet Wygwam