Discussion :

[pouii]

bonsoir a tous
excusé moi si jsui pas sur le bon forum, je savia pa tro ou le posté.

donc mon problème est que je recherche le tri dichotomique

après de nombreuses heures de recherche sur le net, je n'ai pas trouvé !
en effet la plupart des sites me montre la recherche dichotomique que je conné déja.
ca montre aussi que le tri dichotomique est le tri rapide alors que jen suis sur que c'est pa sa !(sauf si vous pouver me certifié le contraire )

merci beaucoup de votre aide

[jobherzt]

après de nombreuses heures de recherche sur le net, je n'ai pas trouvé !

ben voyons...

http://www.google.fr/search?hl=fr&sa...omique&spell=1

[pouii]

mwé
comme j'ai dit le tri rapide n'st pas un tri dichotomique

dev paradise propose un algo illisble que j'ai esseyé de décortiquer sans résultat, c'est pas que j'ai pas esseyé mais bon c'est pas tro de mon niveau, je sui qu'un débutant...

le tri par insertion c'est pas sa non plus

ba tant pis, jvé continué mes rechreche

merci beaucoup

[poof65]

Ca n'existe pas un tri dichotomique.
C'est plutôt une méthode à utiliser dans des algos de tri ou de recherche.

[souviron34]

d'abord parle le français....

Et ensuite, c'est simple :

tu as une liste
tu sautes à la moitié
tu regardes si c'est à gauche ou à droite.
A gauche : tu divises l'intervalle entre le début et ce point en 2, et tu itères
A droite : tu divises l'intervalle entre ce point et la fin en 2, et tu itères...

[Zavonen]

Il est basé sur l'écriture binaire des entiers:

V=(v0, v1, …, vn-1) désigne un vecteur à n éléments entiers naturels que l'on veut trier par ordre croissant. On rappelle l'algorithme du 'tri par distribution':
a) calculer M=max(v0, v1, … vn-1)
b) Déterminer le plus petit entier K tel que M<2K
c) Pour p=0,1, …, K-1 faire permute(p,V) fin pour.
où l'appel permute(p,V) place en tête de V les éléments dont le bit p vaut 0 et en queue les éléments dont le bit p vaut 1, l'ordre initial des entiers étant conservé à l'intérieur de chaque groupe.

[Hephaistos007]

Les arbres binaire de recherches (ABR) sont des structures de données intrinsèquement basés sur une propriété dichotomique.

[PRomu@ld]

Les arbres binaire de recherches (ABR) sont des structures de données intrinsèquement basés sur une propriété dichotomique.

Attention tout de même, on peut avoir une structure de tas qui respecterai le même principe mais ça n'est pas de la dichotomie. C'est une structure "accélératrice" pour la recherche ou l'insertion d'éléments. La dichotomie sépare en deux la quantité de donnée à chercher, dans le cas d'ABR généraux ou de tas, rien ne garanti une telle division, seul les AVL ou arbres rouges noirs (et tout ABR équilibré en fait) permettent celà.

[Hephaistos007]

Attention tout de même, on peut avoir une structure de tas qui respecterai le même principe mais ça n'est pas de la dichotomie. C'est une structure "accélératrice" pour la recherche ou l'insertion d'éléments. La dichotomie sépare en deux la quantité de donnée à chercher, dans le cas d'ABR généraux ou de tas, rien ne garanti une telle division, seul les AVL ou arbres rouges noirs (et tout ABR équilibré en fait) permettent celà.

C'est quoi un ABR "général" ?

[PRomu@ld]

Je voulais parler d'ABR dont tu ne connais rien de son équilibre. S'il est mal construit, tu peux éventuellement te retrouver avec une liste chaînée, dans ce cas la recherche ne va pas diviser par deux le nombre de donnée à chercher mais seulement le réduire d'un. Alors bien sur, on peut prouver qu'un arbre construit aléatoirement va être en moyenne "sympatique" (ne dégénérera que dans de rare cas) et que la recherche d'un élément va se faire avec une complexité logarithmique (et donc par hypothèse d'un arbre binaire diviser par deux les données à chercher à chaque itération) , mais ceci n'est qu'une moyenne.

[pseudocode]

[hors-sujet]
un bon truc pour jouer avec les arbres: behaviour of binary search trees
[/hors-sujet]

[amine6441]

salut mon ami pour la recherche dichotomique qui est conssue juste pour rechercher dans un tableau trie et son avantage c'est qu'elle est tres rapide
je vais te donne un example mais n'oubli pas que la recherche ecotomique ne fanctionne que dans un tableau trie

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
procedure rechercher(var t:ttab,ele:entier,var pos : entier)
var bi,bs,mil:entier;
trouve:boolean;
debut
bi=1;bs=n;pos=0;trouve=faux;
tant que(bi<bs)et(non trouve)faire
debut
mil=(bi+bs)dive2;
sit[mil]=elem alors debut
trouve=vrais;
pos=mil
fin
sinon
si t[mil]>elem alors debut
bs=mil-1;
bi=mil+1;
fin
fin
fin
fin