Considere o problema de pesquisa:

Entrada: Uma seqüência de n números A = <a₁, a₂, ..., a_n> 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] )