Discussion :

[oc_alex86]

Bonjour,

J'ai un séquence de 5 nombres n0 .. n5 tous dans un intervalle [0,r] qui vérifient la propriété
n0 <= n1 <= n2 <= ... <= n5.
Mon but est de trouver une façon de les lister tel que, si on me donne un élément de la liste, je peux connaitre facilement sa position dans la liste.

Malheureusement, je ne vois pas du tout comment faire ça.

[edfed]

s'il n'y à que 5 éléments dans la liste, le problème ne se pose même pas, suffit de parcourir la liste, et comparer chaque élément avec le nombre en entrée, et dès qu'on en trouve un égal, on a la position.

ça peut même fonctionner pour des listes de taille énorme, avec la vitesse des processeurs, ça ne pose aucun problème de parcourir des listes de plusieurs millions d'entrées. au delà, ça peut être plus lent.

[estelle.bod]

La recherche par dichotomie peut être plus rapide et elle est possible puisque votre tableau est trié

[souviron34]

+1 pour la dichotomie (pour des nombres quand même largement supérieurs à 5)..

Sinon, pour des nombres pour lesquels une dichotomie ne se justifie pas forcément, un test simple :

milieu = N/2

Si valeur <= valeur(milieu)

cherche pour i = milieu jusqu'à i >= 0

Sinon

cherche pour i = milieu jusqu'à i < N

[oc_alex86]

Il n'y a donc aucun moyen simple d'accéder à l'élément souhaiter?
Je dois tout de même accéder environ 2^30 fois à un élément dans une table de 10 Mo, ce qui n'est pas rien.

[Nebulix]

2^30 fois ?
Il y a un pb d'algo en amont !

[souviron34]

@P.O. :

Tu ne nous a pas donné correctement le rpoblème :

J'ai un séquence de 5 nombres n0 .. n5 tous

ce n'est pas :

un élément dans une table de 10 Mo,

D'autre part :

2^30 fois ?
Il y a un pb d'algo en amont !

Absolument....





Peut-on savoir ce que tu cherches réellement à faire ????

Expose ton vrai problème, clairement, et tu auras (peut-être) des réponses correctes...


(en remarque : la dichotomie est quasi-imbattable sur d'énormes nombres)