Algorithmique

Mina : "je dois trouver un algorithme en O(log n)"
gravgun : "ça peut se faire en O(n)"

Oups ^^'

Pour faire du O(log n) tu as la recherche par dichotomie.

Cependant la question de gravgun est pertinente, qu'est-ce que tu entends par "ll manque un et un seul entier dans le tableau". Les entiers existent en nombre infinis, alors quel est le sous ensemble que tu manipules ?

J'maitrise pas trop la notation O(x), et de l'algo j'en mange pas trop ^^
M'enfin j'ai dit que c'était une "idée" hein :)

Merci pour la réponse mais je cherche un algorithme en O(log n )

@MinaAlors réponds à notre question, quel est le sous ensemble que tu manipules ?

Si tu as par exemple tous les entiers entre 1 et n (sauf celui qui manque) tu sais déjà où chaque entier doit se placer. Par dichotomie tu regardes à partir de quand c'est décalé.

En gros :

j = n/2
k = n/2

Tant Que j != 1

    j = j/2

    Si tab[k] == k
        k = k-j
    Sinon
        k = k+j
    Fin Si

Fin Tant Que

Afficher "Il manque" k

gravgun thnx pour l'idée KX thnx for you too.
l ensemble est de [1..n], par exemple si j ai un tableau qui contient : 0 1 2 3 4 6 7 l'algorithme doit retourner 5.
Avec la dichotomie ça me semble pas mal comme idée mais je trouve pas comment je pourrais faire exactement.....
Par exemple , utilisant la même tableau , si je dévisse le tableau en deux je trouve que m=3 et t[m]=3 si je fais la comparaison
je trouve que t[m-1]+1 = t[m]
t[m+1] -1= t[m]
donc je vais me déplacer ou après ??!!!!