Loop Invariante

Entrada: Uma seqüência de n números A = <a1, a2, ..., an> e um valor v.

Saída: Um índice i tal que v = A[i] ou o valor especial NIL, se v não aparecer em A.

Escreva um pseudocódigo para pesquisa linear, que faça a varredura da seqüência, procurando por v. Usando um loop invariante, prove que seu algoritmo é correto. Certifique-se de que seu loop invariante satisfaz às três propriedades necessárias.

Solução:


A seguir, encontra-se o pseudocódigo para a pesquisa linear:

PesquisaLinear(A, n, v)



1   for i ← 1 to n

2         do if A [i] = v

3               do return i

4   return NIL 

Seu loop invariante é:

Loop Invariante:

( ( v = A [i] ) e ( i < n ) ) ou ( v   A [1 .. i - 1] ) 

( ( v = A [i] ) e ( i < n ) ) ou ( v   A [1 .. i - 1] )