La dichotomie

[Remyy]

Bonjour, j’ai un problème en numérique et sciences informatiques : 

TAB = [0;2;4;6;8;10;12;14;16;18;20;22] (un tableau d’entier)

on utilise un algorithme de recherche dichotomique pour chercher si le nombre 11 est présent dans le tableau.

Quels seront les sous-tableaux parcourus lors de cette recherche?

Meme question avec le nombre 20.

 

alors qu’elle seront ces sous-tableaux et quel est l’algorithme qui permet de voir cela?

merci d’avance pour votre aide 

[julesx]

Bonsoir,

 

Si le tableau est trié, ce qui est le cas, une approche possible :

Tu divises le tableau en 2 parties, gauche et droite. Si le tableau contient un nombre impair d'éléments tu prends pour celui de gauche le plus petit des deux.

Si le nombre N dont tu cherches la présence et supérieur au nombre le plus grand de la partie gauche, tu conserves la partie droite, sinon tu conserves la partie gauche.

Avec la partie conservée, tu recommences la démarche précédente.

Tu fais cela jusqu'à ce que la partie conservée ne comporte plus qu'un seul terme.

Dans ce cas, deux possibilités:

* Le terme est égal au nombre recherché, dans ce cas, il y a présence du terme N dans la liste.

* Il n'y a pas égalité,  N ne fait pas partie de la liste.

 

Exemples avec tes données :

 

TAB = [0;2;4;6;8;10;12;14;16;18;20;22]

Les deux parties sont [0;2;4;6;8;10] et [12;14;16;18;20;22]

11 est supérieur à  10, donc on conserve [12;14;16;18;20;22]

Les deux parties sont [12;14;16] et [18;20;22]

11 n'est pas supérieur à 16 donc on conserve [12;14;16]

Les deux parties sont [12] et [20;22]

11 n'est pas supérieur à 12 donc on conserve [12]

Comme il ne reste qu'un terme et qui est différent de 11, 11 ne fait pas partie de la liste.

 

TAB = [0;2;4;6;8;10;12;14;16;18;20;22]

Les deux parties sont [0;2;4;6;8;10] et [12;14;16;18;20;22]

20 est supérieur à  10, donc on conserve [12;14;16;18;20;22]

Les deux parties sont [12;14;16] et [18;20;22]

20 est supérieur à 16 donc on conserve [18;20;22]

Les deux parties sont [18] et [20;22]

20 est supérieur à 18 donc on conserve [20,22]

Les deux parties sont [20] et [22]

20 n'est pas supérieur à 20  donc on conserve [20)

Comme il ne reste qu'un terme et qui est égal à 20, 20 fait partie de la liste.

 

Ceci te permet en particulier d'identifier les sous-tableaux.

Pour l'algorithme, essaie de voir ce que cela peut donner. Bon courage...

 

[julesx]

Petits compléments :

Dans ce qui précède, je n'ai envisagé que les cas strictement supérieur ou strictement inférieur. Si N est égal au nombre le plus grand de la partie gauche, il est inutile d'aller plus loin, ce nombre est évidemment bien présent. Ceci réduit éventuellement le nombre de sous-tableaux à envisager. A titre d'exemple, pour N=10, on a, dès la première séparation, l'égalité avec le terme maximum de [0;2;4;6;8;10], donc la recherche s'arrête là.

Un exemple d'algorithme utilisant un démarche légèrement différente est donné ici

https://fr.wikipedia.org/wiki/Recherche_dichotomique#Écriture_itérative