Menu

Algorithme de recherche dichotomique [Fermé]

maya80 52 Messages postés mercredi 3 novembre 2004Date d'inscription 28 juillet 2010 Dernière intervention - 10 nov. 2009 à 04:27 - Dernière réponse : maya80 52 Messages postés mercredi 3 novembre 2004Date d'inscription 28 juillet 2010 Dernière intervention
- 10 nov. 2009 à 14:47
Bonjour,
Voilà, j'ai ce problème qui est très urgent:

Étant donné un tableau trié t de n nombres entiers, on veut appliquer la recherche dichotomique, supposons que le tableau t contient m éléments, dont presque tous sont égaux à l'infini (disons le plus grand entier pouvant être stocké dans un mot de mémoire). Plus précisément, supposons que les valeurs finies (< infini) sont stockées aux indices compris entre 1 et n et que n est beaucoup plus petit que m. Dans un tel tableau, la fouille dichotomique prend un temps proportionnel à logm. Décrivez un algorithme de recherche dichotomique qui détermine, en un temps dans O(log n) (et non O(logm)), si un nombre x < infini apparaît dans t ou non.

Ce que je veux savoir, c'est comment ecrire un algorithme qui soit de complexité logn alors que la taille du tableau est m.
Merci à tout le monde.
Afficher la suite 

2 réponses

adns 1100 Messages postés vendredi 23 février 2007Date d'inscription 27 mars 2012 Dernière intervention - 10 nov. 2009 à 12:05
0
Utile
bonjour

si j'ai bien compris ton énonce tu as un tableau couper en 2 parties
la premiere de 1 à n avec les valeur < infini
la deuxieme de n a m avec les valeur "> infini"

je me plante peut etre mais ca me parait simple il te suffit de faire une recherche dichotomique en allant de 1 à n .....

non ?

Adns
maya80 52 Messages postés mercredi 3 novembre 2004Date d'inscription 28 juillet 2010 Dernière intervention - 10 nov. 2009 à 14:47
0
Utile
Honnetement, j'ai pensé à cette réponse, mais elle me parrait tellement simple que je doute un peu.
Je veux seulement savoir s'il n'y aurait une autre solution.
Merci.