Algorithmique : recherche dichotomique, fin + debut / 2 Résolu/Fermé

Question

Hello tout le monde,

J'aurais besoin de précision au sujet de la recherche dichotomique, et plus exactement dans la logique utilisé pour concevoir son algorithme.

Le principe de dichotomie comprit, j'ai fais un exercice et vu sa résolution dans mon support de cours ; un passage m'interpelle :

Variables...Initialisation...TraitementTantque     mil ? partie entière( (début + fin) / 2)     ...FTantqueSortie...



On est d'accord que l'instruction
mil ? partie entière( (début + fin) / 2)
a pour but d'obtenir le MILIEU d'une échelle allant de DEBUT à FIN.

Cependant, à ce titre, ce qui me vient plus logiquement (selon moi uniquement peut-être), c'est 
mil ? partie entière( (fin - début) / 2 + debut)
Je procède de manière à obtenir le milieu de la "taille" de la partie à analyser (fin - debut/2) puis j'y ajouter le début de l'échelle qu'on a auparavant déterminé(+ début) de manière à " positionner " le curseur au bon endroit.

Le résultat escompté est le même - mais la solution proposé par mon support de cours est plus courte, donc avec une meilleur scalabilité, et est donc à privilégié.. 

Y'a t'il donc une notion de mathématique qui m'échappe et qui m'empêche de parvenir à cette optimisation ? (Une sorte de vérité général tel que (A+B)/2 = (B-A)/2+A qui m'aurait complètement échappé). Si oui, comment pourrais-je acquérir ces notions sensées optimiser mes algorithmes ?
Vous comprendrez que c'est davantage un problème de conception à long terme qu'un souci de compréhension de cet algorithme en particulier. En conditions réelles je sais que ça peut ralentir l'expérience utilisateur, surcharger des serveurs, ralentir le développement en équipe (" pourquoi il a fait ça ? ") etc.

Bref, si quelqu'un pouvait m'aider je lui en serai reconnaissant :)

Bonne navigation !

Pour vous renseigner sur mon niveau, dans l'optique de me construire de solides connaissant en algorithmique (mon parcours a débuté par l'intégration web) j'aborde en ce moment les bases : qu'est-ce que les mathématique sont, comment les logiciens forment une branche des mathématique, qu'est-ce qu'un algorithme et enfin les principaux algorithmes (dont la dichotomie).

KX · Accepted Answer

mil &larr; partie entière( (début + fin) / 2)
Ici c'est la moyenne de début et fin qui est utilisé, donc ça donne bien le milieu.

mil &larr; partie entière( (fin - début) / 2 + debut)
Là tu réfléchis un peu différemment (et tu n'es pas le seul), mais c'est aussi le milieu.

À la partie entière près, les deux calculs sont mathématiquement équivalents.
(x+y)/2 = x/2 + y/2 = (x - x/2) + y/2 = x + y/2 - x/2 = x + (y-x)/2
En terme d'optimisation, (début+fin)/2 fait deux opérations (une addition, une division), alors que (fin-début)/2+début en fait trois (une soustraction, une division, une addition), donc le premier calcul est moins lourd.

Attention : (début+fin) étant plus grand que début et fin, il peut y avoir un dépassement numérique (c'est à dire qu'on peut obtenir un nombre qui est trop grand pour être représenté dans le type de donnée qu'on a attribué à début et fin), du coup le résultat peut devenir faux.
En faisant (fin-début)/2+debut on est sûr de rester dans l'intervalle de valeurs debut &rarr; fin, et donc d'avoir des résultats numériques corrects. Mais c'est un cas assez particulier vu que ce problème ne peux se poser que pour des données extrêmes et uniquement à la première itération de ton algorithme de dichotomie.La confiance n'exclut pas le contrôle

Rollover · Answer

EDIT : A la place du " mil ? partie entière (...) ", il s'agit de " mil = partie entière (...) "

Algorithmique : recherche dichotomique, fin + debut / 2

2 réponses

Discussions similaires