Bonjour,
Quelqu’un pourrait-il me donner un invariant de boucle de l’algorithme de recherche dichotomique s’il vous plaît?
Merci
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 :
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.»
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
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
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager