CommentCaMarche
Recherche
Posez votre question Signaler

Algorithme de recherche dichotomique

maya80 53Messages postés mercredi 3 novembre 2004Date d'inscription 28 juillet 2010Dernière intervention - Dernière réponse le 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.
Lire la suite 
Réponse
+0
moins plus
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
Ajouter un commentaire
Réponse
+0
moins plus
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.
Ajouter un commentaire
Ce document intitulé «  Algorithme de recherche dichotomique  » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes.

Le fait d'être membre vous permet d'avoir des options supplémentaires.