Signaler

Algorithme de recherche dichotomique

Posez votre question maya80 52Messages postés mercredi 3 novembre 2004Date d'inscription 28 juillet 2010 Derniè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.
Afficher la suite 
Utile
+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
Utile
+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

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.

Vous n'êtes pas encore membre ?

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