Discussion:Recherche dichotomique

Question de 2003

Que veux-tu dire par : "On suppose bien sûr qu'il existe un test relativement simple permettant à chaque étape de déterminer l'une des deux parties dans laquelle se trouve une solution." ?
Clifford 10 jun 2003 ・10:16 (CEST)

Le "relativement simple" est sans doute superfétatoire. Sinon, ben à chaque étape, on coupe le domaine de recherche en deux, et on demande à un oracle "dans laquelle de ces deux parties continuer à chercher?" -- voilà ce que je voulais dire. Je voulais rédiger l'article de façon à ce qu'il soit compatible avec l'existence de plusieurs solutions, dont on n'en recherche qu'une (si il en existe). Ça rend le texte plus général et plus correct, mais peut paraître bizarre à la lecture. C'est peut-être une mauvaise idée. Fais mieux si tu peux. -- Faré 10 jun 2003 ・10:33 (CEST)

Itératif ?

Je me suis permis une légère modification à votre texte : la dichotomie est un processus qui peut être décrit par un raisonnement itératif, mais on le voit plus souvent sous sa forme récursive. Si vous n'êtes pas d'accord, je ne serais pas vexé que vous supprimiez cette modif. Merci pour la qualité de vos définitions D. FROELIGER (eXia)

Autre sens ?

J'ai déplacé du corps de texte cette remarque

La dichotomie est également une maladie.

Car je n'en trouve trace dans aucun dictionnaire même médical. Le seul sens concernant la dichotomie dans le milieu médical concerne une pratique illégale de partage d'honoraires entre médecin généraliste et médecin spécialiste. HB 19 juillet 2006 à 17:44 (CEST)

Méthode de dichotomie

Cette page est plus générale que Méthode de dichotomie, le paragraphe Autre exemple couvrant le même sujet d'une manière simplifiée. Pourquoi ne pas les fusionner ?Jct 15 novembre 2006 à 15:06 (CET)

Critiques sur l'algorithme

Je me permets de critiquer la rédaction de cet article notamment au niveau de l'algorithme.

Tout d'abord, nous ne savons pas ce que va faire l'algorithme. Aucune phrase expliquant le but de l'algorithme. Ensuite, si je comprends bien l'algorithme recherché demande une valeur à chercher et renvoie la valeur à chercher. Ce qui n'a vraiment aucun intérêt. En effet, il n'y a aucun intérêt à chercher une valeur que nous connaissons déjà...

Si vous cherchez à savoir si une valeur appartient à l'ensemble, il vaudrait mieux renvoyer une valeur booléenne.

Oui d'autant que tel quel l'algorithme affiche toujours la même chose que la valeur appartienne ou pas au tableau. Par ailleurs la saisie de la valeur à chercher est dans une boucle (pourquoi ?) manifestement incorrecte.

Algorithme modifié dites moi si vous êtes d'accord...

Champ d'application : Utilisation du Dictionnaire.

Dans la partie champs d'application, nous pourrions parler de l'utilisation du dictionnaire non ? cela me parait être l'exemple le plus fréquemment utilisé de recherche par dichotomie, même si pratique on fait des adaptation (on cherche renard, on n'ouvre pas tout à fait le dictionnaire au milieu mais un peu plus vers la fin, et si on est très proche on tourne les pages plutôt que d'estimer le milieu, mais c'est très approchant). Cronseaux 24 mai 2007 à 11:31 (CEST)

Meilleur facteur de division pour la recherche dichotomique

On m'avait prouvé que la recherche dichotomique est encore plus optimisée lorsque l'espace de recherche est découpé au tiers plutôt qu'à la moitié.

C'était une preuve par les suites arithmétiques (je crois) et en TP, ça marchait, c'était plus rapide.

Est ce que vous pourriez dire un mot là dessus ?

Je me souviens d'une démonstration en prépa (il y a un bail) que l'optimum constait à découper l'intervalle par e=2.7 et donc en 3 parties égales plutôt qu'en deux, mais que cela n'était pas fait en pratique car plus difficile à programmer. Si quelqu'un peut développer... Skiff (d) 2 février 2009 à 12:49 (CET)

Article sur même sujet

Voir Méthode_de_dichotomie. -- Saippuakauppias ⇄ 15 juin 2009 à 23:33 (CEST)

Algorithme faux

La partie de l'algorithme qui suit est fausse :

  //Boucle de recherche
  Répéter
   mil ← partie entière( début + ((fin-début) / 2) )
   Si t[mil] = val alors
     trouvé ← vrai
   Sinon
     Si val > t[mil] Alors
       début ← mil
     Sinon
       fin ← mil
     FinSi
    FinSi
  Tant que (trouvé=faux et ( début < fin ))

Supposons par exemple qu'on soit parvenu à une étape du calcul où début = 1, fin = 2, t[1] = 3, t[2] = 4 et que val = 4. L'algorithme définit alors mil ← 1 (partie entière de 3/2). Puis, comme val = 4 > t[mil] = t[1] = 3, alors l'instruction début ← mil ne change en rien la valeur de début. Bref, l'algorithme boucle indéfiniment. On évite cet inconvénient en posant début ← mil+1 et fin ← mil-1. Theon (d) 5 juillet 2010 à 08:24 (CEST)

oui, tu as raison, je fais amende honorable ;-) le pb à mon avis, c la présentation de l'algo avec un tableau et des indices (qui sèment la confusion). Ne serait-ce pas mieux de mettre un algo sans tableau dont l'intérêt saute plus aux yeux ? (!). Je propose un algo de dicho "ordinaire" pour approcher un zéro de fonction :

dichotomie - 05.07.2010

1 VARIABLES

2 a EST_DU_TYPE NOMBRE

3 b EST_DU_TYPE NOMBRE

4 c EST_DU_TYPE NOMBRE

5 esp EST_DU_TYPE CHAINE

6 DEBUT_ALGORITHME

7 esp PREND_LA_VALEUR " - "

8 a PREND_LA_VALEUR 0

9 b PREND_LA_VALEUR 1

10 TANT_QUE (abs(F1(b)-F1(a))>0.01) FAIRE

11 DEBUT_TANT_QUE

12 c PREND_LA_VALEUR (a+b)/2

13 SI (F1(c)*F1(b)<0) ALORS

14 DEBUT_SI

15 a PREND_LA_VALEUR c

16 FIN_SI

17 SI (F1(a)*F1(c)<0) ALORS

18 DEBUT_SI

19 b PREND_LA_VALEUR c

20 FIN_SI

21 AFFICHER a

22 AFFICHER esp

23 AFFICHER b

24 FIN_TANT_QUE

25

26 FIN_ALGORITHME

Fonction numérique utilisée : F1(x)=pow(x,3)+x-1

--Axel (d) 5 juillet 2010 à 18:45 (CEST)

L'algorithme que tu proposes ferait double emploi avec celui déjà présent dans l'article dans le paragraphe autre exemple. L'article tel qu'il est me paraît assez équilibré, avec un algo pour une structure indicée, et un algo pour des nombres flottants. Theon (d) 6 juillet 2010 à 09:05 (CEST)

Améliorer peu à peu cet ajout d'algorithme du 16/12/06 me semble une fausse bonne idée : ça reste du TI et WP n'est pas une banque d'algos donc § à supprimer. Anne (d) 28 février 2013 à 23:34 (CET)

+1 HB (d) 3 mars 2013 à 17:42 (CET)

Enlever le premier exemple ?

Bonjour,

je pense enlever le premier exemple, ou bien le raccourcir franchement. Qu'en pensez-vous ?--Roll-Morton (discuter) 2 juillet 2014 à 11:16 (CEST)

Ce serait dommage de supprimer : c'est la seule partie accessible au profane ( et ressemblant d'ailleurs à la finale d'un jeu télévisé). Il permet de comprendre la méthode employée pour résoudre une équation du type f(x)=0. Tout le reste (l'algorithmique, la complexité), qui a certes sa place dans l'article, est probablement hors de portée du lecteur moyen. En revanche on peut probablement se passer du commentaire suivant : « La dichotomie peut être vue comme une variante simplifiée de la stratégie plus générale diviser pour régner » qui n'a à mon avis rien à voir avec ce qui nous intéresse.HB (discuter) 2 juillet 2014 à 12:17 (CEST)

Je suis d'accord avec le fait qu'il faut garder quelque chose dans ce gout là, mais je trouve que tel quel cela prend beaucoup de place avec une présentation pas très agréable : personne ne va lire 6 fois la même phrase je pense. Et je suis d'accord pour enlever ce que tu cites.--Roll-Morton (discuter) 2 juillet 2014 à 13:32 (CEST)

Ah oui, j'aurais du préciser que j'étais en revanche d'accord pour qu'on allège eventuellement la section. HB (discuter) 2 juillet 2014 à 14:35 (CEST)

Je vais tenter un changement rapide. --Roll-Morton (discuter) 2 juillet 2014 à 14:43 (CEST)

 HB : Voilà. --Roll-Morton (discuter) 2 juillet 2014 à 14:47 (CEST)

 HB : Que penses-tu de prendre comme exemple l'image qui est actuellement en tête d'article ? Je pense que cela est suffisant pour avoir une bonne idée de l'algorithme. Par contre, on ne se rend peut-être pas compte que le nombre d'étapes est très petit, on pourrait rajouter une phrase du type « dans un dictionnaire, l'algorithme fait tant d'étapes ». --Roll-Morton (discuter) 29 juin 2016 à 20:04 (CEST)

Changement : homonymie, recherche dichotomique etc.

J'ai proposé des changements ici. --Roll-Morton (discuter) 27 mai 2016 à 11:37 (CEST)

Retrait «Champ d'application» ?

Bonjour, la partie «Champ d'application» n'est pas super je trouve, et pas sourcée. Je pense l'enlever, pour éventuellement reconstruire une section « utilisation » ou « application » plus tard. Des avis ? --Roll-Morton (discuter) 29 juin 2016 à 20:06 (CEST)

 Valéry Beaud, Jacques Ghémard, Faré, Cos, Yanngeffrotin et Gevehef : Un avis ? --Roll-Morton (discuter) 7 novembre 2016 à 19:43 (CET)

Le contenu de cette partie est peu expressif par rapport à son sujet, il laisse plutôt l'apparence d'un doublon par rapport à la partie « Exemple introductif » (d'ailleurs, on y voit plusieurs « par exemple »).
Donc il n'est pas forcément nécessaire de le supprimer. Ce qui compte est de le réécrire, en conservant le premier paragraphe, en supprimant les trois suivants, puis en complétant tout cela par d'autres domaines (plus ou moins concrets) comme celui cité de l'industrie, le travail, les statistiques, la mécanique, la programmation, la vie, etc.
En gros, sont concernés tous les cas comprenant au moins un certain nombre d'éléments (au moins trois). Cela pourra d'ailleurs faire un lien avec l'UML et ses diagrammes de séquence ou d'activité.
--Gevehef (discuter) 9 novembre 2016 à 12:55 (CET)

 Gevehef : Merci pour l'avis. Je partage ce point de vue. Je vais résumer. Par contre je n'ai pas d'exemple d'application non-inventé sous le coude, en particulier je ne connais pas l'UML. --Roll-Morton (discuter) 10 novembre 2016 à 15:32 (CET)

Algorithme récursif faux

De multiples changements intervenus ces jours-ci sur l'algorithme récursif montre qu'il y a un problème certain.

• L'algorithme est pourtant parfaitement sourcé et me semblait parfaitement conforme à la source dans sa version initiale introduite 8 décembre 2016
• Mais très rapidement cet algorithme est modifié et devient à mon avis faux : on voit tout de suite que l'algorithme (version du 8 dec à 11:08) compte tantôt les indices à partir de 0 et tantôt à partir de 1 et n'incrémente pas l'indice s'il faut chercher dans la seconde partie de la liste
• Passons sous silence les modifs peu glorieuses de mai 2020[1], [2] où je tente de réparer (mal) ce qui était cassé
• Bonne intervention en aout 21 qui répare partiellement le pb en remettant une incrémentation quand on est dans la seconde moitié de la liste
• en décembre 2022 quelqu'un se pose la question du cas m = 0 qui risque de faire un erreur si les éléments de la liste sont indexés de 1 à n
• aujourdhui, 10 mars quelqu'un fait sauter ce verrou

Soyons clair, je ne sais pas programmer en Python mais j'ai assez de bouteille pour voir qu'il y a encore un pb dans la version actuelle

1. (a) si on compte à partir de 1, une liste de longueur 1 donne m=0 et une erreur quand on cherche "liste triée (m)" (il me semble qu'il faudrait prendre m=(len +1)/2 ) - (b) si on compte à partir de 0, on ne doit pas tronquer le début de liste en prenant "liste triee [1:m]"
2. l'instruction "liste donnée [i:k]" semble extraire de "liste donnée" tous les éléments de l'indice i à l'indice k mais ne connaissant rien en python je ne sais pas si cette extraction donne une liste indexée de i à k ou de 0 à k-i ou de 1 à k-i+1. Or cette connaissance est nécessaire pour valider l'ensemble de l'algorithme

La source citée n'offre peut-être pas une version optimale, suppose l'existence de l'élément dans la liste, indexe de 0 à len -1, obtient une sous-liste indexée à partir de 0 mais nonobstant tout cela elle offre l'avantage .... d'être sourcée et de me paraitre sans erreur de code. Je la remet donc. HB (discuter) 10 mars 2023 à 15:21 (CET)

En accord. Je mettrais aussi un commentaire indiquant : pas de changement sans source. On voit où cela mène, de fil en aiguille. Jean-Christophe BENOIST (discuter) 10 mars 2023 à 15:25 (CET)

Mis en place mais en fait ce n'est pas un pseudocode mais une implémentation (je ne sais pas faire en pseudo-code sans me laisser influencer par le langage que je vais utiliser)

mauvais programme python

cet article est assez typique pour l'enseignement français, il rend compliqué et tordu un truc vraiment très simple a priori, la recherche dichotomique.

Le programme python est mauvais pour plusieurs raisons :

• il renvoie 0 quand la liste est de longueur 1, c'est aussi inutile que faux

• il recherche dans L[m:] alors qu'on sait que x != L[m]

• la récursivité c'est parfois bien mais pour la recherche dichotomique une simple boucle "while" qui ajuste progressivement l'indice mini et maxi est plus efficace et simple.

Initialisation : a,b = 0, len(L)-1 au départ (si vous voulez, gauche,droite ou début,fin au lieu de a,b)

Tant que a <= b, on compare x à L[m := (a+b)//2 ] et si c'est = on renvoie m, si c'est inférieur on pose b=m-1 (!) et sinon on pose a=m+1.

Si la boucle termine car a>b, on renvoie "non trouvé". C'est simple et logique.

— MFH 3 juin 2023 à 01:51 (CEST)