Petite question au sujet de la dichotomie - Page 1

Lorsque la valeur recherchée n'existe pas, l'algorithme de recherche par dichotomie s'arrête-t-il toujours sur la valeur immédiatement inférieure, ou peut-il aussi bien s'interrompre sur la valeur suivante (peut-être que ça dépend de l'implémentation ?) ?

Et si vous n'avez pas trop la flemme d'expliquer : Pourquoi ?

Merci

Tout depend du nombre diteration sur ta dichotomie..
tu peux tres bien t'arretter sur la valeur qui minore tout comme la suivante sur la majoration..

Cela depend aussi de l'implémentation: cela depend si comme nouvelle borne (inférieure ou supérieure selon l'itération) tu prends la partie entiere de (BorneSup - BorneInf) ou celle de partie entiere de ((BorneSup - BorneInf) + 1); Les deux fonctionnent normalement.

Merci à vous donc à la fin de la dicho je n'ai pas d'autre choix que de "descendre" dans la liste tant que n'est pas trouvé un élément inférieur

oué, et c pas forcement plus rapide qu'un pourcour linéaire optimisé ...

La dicho est toujours plus rapide dans les grandes listes

pour moi la recherche dichotomique c'est ça :

int recherche(int *tab, int n)
{
   int inf, sup, mid, trouve;

  inf = 0;
  sup = n;
  trouve = false;
  while (inf < sup && trouve == false) {
    mid = (inf + sup) / 2;
    if (valeur < tab[mid])
      sup = mid;
    else if (valeur > tab[mid])
      inf = mid + 1;
    else
      trouve = true;
  }
  return trouve
}

le nombre d'itérations est majoré par : sup( ln(n) / ln(2) )
sup étant l'arrondi à la valeur entière supérieure

Thibaut a écrit :
La dicho est toujours plus rapide dans les grandes listes

Ça dépend de ce que tu appelles "liste". Pour de grands tableaux, oui. Pour de grandes listes chaînées, il me semble bien que non! Tu parcours ta liste chaînée plein de fois si tu essayes de faire de la dichotomie avec des listes chaîneées.

C'est évident Kevin, même le plus idiot des programmeurs peut le deviner. Halàlà ce Kevin


jcop : oui c'est ça.

a mon avis si on veut faire une liste dans laquelle il y auras beaucoup de recherche il vaut mieux utiliser un tableau normal !

surtout que les listes chainées, sur TI... vu le peu de handle qu'il y a...

C'est quoi ce que tu appelles un tableau normal ? (je crains que tu ne répètes Kevin )

int tab[N];

en gros

Oué ben il n'a fait que répéter Kevin

pour les listes chainées, on peut utiliser genalib qui premet de gerer plein de petits blocs memoire (avec 1 seul handle)