Invariant de boucle

Bonjour,
Quelqu’un pourrait-il me donner un invariant de boucle de l’algorithme de recherche dichotomique s’il vous plaît?
Merci

On part du code qui requiert un tableau array trié et qui renvoie soit l'indice dans array de la valeur cherchée si array la contient, -1 sinon :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 dsearch( value, array ) begin found = false left = 0 right = array.length-1 while not found and left<=right do median = (left+right) div 2 if array[median]==value then value = true else if array[median]<value then left = median + 1 else right = median - 1 end if end if end while return found?median:-1 end
Dans ce code je t'ai écrit la conditionnelle sous une forme un peu explosée, mais elle te permet de trouver facilement un invariant de boucle de la forme «soit la valeur est trouvée et found est vrai, soit on réduit l'intervalle du tableau susceptible de contenir value par rapport à l'itération précédente.»

Merci beaucoup!

Modification

Bonjour WhiteCrow,

Je crois que la ligne 10 : value = true devrait être found = true.

Citation:

Envoyé par WhiteCrow

...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
dsearch( value, array )
begin
    found = false
    left = 0
    right = array.length-1
    while not found and left<=right do
        median = (left+right) div 2
 
        if array[median]==value then
            value = true
        else
            if array[median]<value then
                left = median + 1
            else
                right = median - 1
            end if
        end if
 
    end while
 
    return found?median:-1
end

...

Salut

Merci !
Je corrige le message en conséquence.

Edit:
Malheureusement le message est trop ancien pour la correction. Je la publie donc ici:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
dsearch( value, array )
begin
    found = false
    left = 0
    right = array.length-1
    while not found and left<=right do
        median = (left+right) div 2
 
        if array[median]==value then
            found = true
        else
            if array[median]<value then
                left = median + 1
            else
                right = median - 1
            end if
        end if
 
    end while
 
    return found?median:-1
end