Discussion :

[AI_user02000]

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

[WhiteCrow]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.»

[AI_user02000]

Merci beaucoup!

[Guesset]

Bonjour WhiteCrow,

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

...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[WhiteCrow]

Merci !
Je corrige le message en conséquence.

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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