Algo général de recherche dichotomique après un trie bubble sort
Soyez le premier à donner votre avis sur cette source.
Snippet vu 20 276 fois - Téléchargée 28 fois
Contenu du snippet
Le code suivant (écrit en C++) effectue dans un premier temps le Trie Bubble Sort d'un tableau. Par la suite une Recherche Dichotomique (Code en Algo) vient compléter le tout.
Lors d'une recherche Dichotomique la borne supérieure ou inférieure du tableau est modifiée.
Par conséquent, le tableau n'est plus parcouru dans son ensemble, la Recherche en est d'autant Plus Rapide.
Note: Le trie Bubble Sort n'est pas le plus optimisé...
Attention : "La Recherche Dichotomique s'effectue toujours sur un Tableau Trié."
Lors d'une recherche Dichotomique la borne supérieure ou inférieure du tableau est modifiée.
Par conséquent, le tableau n'est plus parcouru dans son ensemble, la Recherche en est d'autant Plus Rapide.
Note: Le trie Bubble Sort n'est pas le plus optimisé...
Source / Exemple :
//Librairies
#include...
//Variables globales
typedef struct
{ char nom_ville[32];
char nom[32];
char tel[11];
}Tindex;
Tindex idx[Max];
int j;
/* Trie Bubble Sort - Création d'un Index trié
en fonction des numéros de téléphones */
void tri_tel_index()
{int k;
Tindex temp[Max];
for(k=Max-1;k!=0;k--)
{ for(j=0;j<k;j++)
{ if((strcmp(idx[j].tel,idx[j+1].tel))>0)
{ temp[0]=idx[j];
idx[j]=idx[j+1];
idx[j+1]=temp[0];
}
}
}
j=0;
}
//Prog. principal
void main() {
...
}
Algo Général de la Recherche Dichotomique
Procedure recherche_dichotomique(par val ent elt, par val ent N, par val ent T[])
Debut
|
| var inf, sup, m;
| inf <- 1;
| sup <- N;
| m <- (inf+sup) div 2;
| /* en C++ m = (int)((inf+sup)/2) */
|
| /* Ici l'astuce : la borne supérieure ou inférieure est modifiée,
| le tableau n'est plus parcouru dans son ensemble */
|
|
| Tant que (T[m] != elt et inf < sup) faire
| |
| | Si (elt < T[m]) alors
| | |
| | | sup <- m - 1;
| | |
| | | Sinon inf <- m + 1;
| | |
| | Fin Si
| |
| | m <- (inf + sup) div 2;
| |
| Fin Tque
|
| Si (T[m] = elt)
| |
| | Afficher("L'element se trouve à l'indice m")
| |
| | Sinon Afficher ("L' élément n'existe pas ")
| |
| Fin Si
|
Fin
Conclusion :
Attention : "La Recherche Dichotomique s'effectue toujours sur un Tableau Trié."
A voir également
- Recherche dichotomique c++
- Recherche dichotomique en c - Meilleures réponses
- Dichotomique - Meilleures réponses
- C / C++ / C++.NET : Algorithme de recherche dichotomique - CodeS SourceS - Guide
- Delphi / Pascal : Recherche dichotomique (exemple avec un tableau) - CodeS SourceS - Guide
- Recherche dichotomique java - Guide
- Recherche dichotomique python - Guide
- Problème recherche dichotomique d'une date ✓ - Forum - Visual Basic 6
Commentaires
je me demande a quoi correspond elt et N de l'algo par rapport au tri a bulle du dessus ???
merci a vous
Je suis tout nouveau ici et
J'essaye d'utiliser cet algorithme pour faire une recherche en maths mais j'ai un bug avec Dev C++ a la ligne Tindex idx[Max];
Pourquoi ? Que Faire ?
Merci à vous si vous avez une idée
bravoo pour cet algo, il m'a permis de faire ma recherche dichotomique en c# du premier coup sans bugger.
Merci.
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.