Como visto em Introdução aos algoritmos http: //mitpress.mit.edu/algorithm), o exercício declara o seguinte:

Input: matriz A [1 ... n]

Saída: i, onde A [i] = v ou NIL quando não encontrado

Escreva um pseudocódigo para LINEAR-SEARCH, que varre a sequência, procurando v. Usando um loop invariável, prove que seu algoritmo está correto. (Certifique-se de que seu invariante de loop atenda às três propriedades necessárias - inicialização, manutenção, terminação.)

Não tenho nenhum problema ao criar o algoritmo, mas o que não entendo é como posso decidir qual é o meu loop invariável. Acho que entendi o conceito de loop invariável, ou seja, uma condição sempre verdadeira antes do início do loop, no final / início de cada iteração e ainda verdadeira quando o loop termina. Normalmente, esse é o objetivo. Por exemplo, na classificação por inserção, passando por j, começando em j = 2, os elementos [1, j-1] são sempre classificados. Isso faz sentido para mim. Mas para uma pesquisa linear? Não consigo pensar em nada, parece simples demais pensar em um loop invariável. Eu entendi algo errado? Só consigo pensar em algo óbvio (é NIL ou entre 0 e n). Muito obrigado antecipadamente!