Discussion :

[Nemerle]

Petit problème qui s'est posé à notre team de dèv., on a une soluce, à voir si c'est optimal en temps de calculs

Considérez une liste L[1]...L[N] d'entiers avec disons N= 100 millions; la forme de cette liste a la propriété suivante: il existe une unique valeur maximale C tel que

- x<y<C entraîne L[x]>=L[y]>=L[C]
- C<x<y entraîne L[C]<=L[x]<=L[y]

Comment trouver le plus rapidement possible C ??

[Jean-Marc.Bourguet]

J'ai l'impression que tu t'es goure dans l'enonce. D'apres ce que tu dis ta liste est triee et n'importe quel indice peut etre C.

Liste pour moi implique un acces sequentiel, est-ce bien le cas?

[Nemerle]

désolé, corrigé: simplement la liste décroit de 1 à C puis croit de C à 100 millions

Pour liste, en fait c'est un array

[Graffito]

Bonjour,

Comment trouver le plus rapidement possible C ??

Une bonne petite recherche dichotomique. (je peux détailler si nécessaire).

[FrancisSourd]

Oui, une recherche dichotomoque sur les L[x+1]-L[x] trouve ton C en O(log N). On ne peut pas faire mieux si on ne connaît pas plus de propriétés "a priori" sur la liste.

[Nemerle]

Bien, maintenant qu'on est tous d'accord, je précise, dans l'algo a implémenter:

- la "forme" du tableau L est connue, mais aucune de ses valeurs n'est connue a priori. Je m'explique: si vous avez besoin de L[500] par exemple, vous devez appeler une fonction qui vous calcule la valeur et qui prend 1/1000 seconde; une fois calculée, vous pouvez la stocker si vous désirez la réutiliser.

- il y a différents "codes" pour implémenter une dichotomie, il faudrait le plus rapide.

J'aimerais bien voir un bout d'algo...