Suponha que n = length. Qual a invariante do ciclo while é key não estar em a, ou

Análise da Questão

Alternativa D

Introdução

Esta questão aborda conceitos fundamentais de Estruturas de Dados e Algoritmos, especificamente sobre a Pesquisa Binária (Binary Search). O objetivo é identificar a invariante de loop, que é uma propriedade matemática que deve ser verdadeira antes e após cada iteração de um laço de repetição, garantindo a correção do algoritmo.

Desenvolvimento

1. O que é uma Invariante de Loop?

Uma invariante de loop é uma afirmação sobre o estado dos dados durante a execução de um loop. Para a busca binária, a invariante essencial é:

"Se a chave key existir no array, ela deve estar localizada no intervalo de índices entre low e high (inclusive)."

Matematicamente, isso se traduz na desigualdade:
a[low] \leq key \leq a[high]

2. Análise do Algoritmo Apresentado

Vamos acompanhar o comportamento das variáveis low e high no código fornecido:

• Inicialização:
• low começa em 0.
• high começa em length - 1.
• Neste ponto, todo o array é considerado. Se a chave existe, ela está entre a[0] e a[length-1].
• Manutenção (Durante o Loop while (low <= high)):
• Calcula-se o meio: mid = (low + high) / 2.
• Caso 1 (a[mid] < key): O valor no meio é menor que a chave. Como o array está ordenado, a chave não pode estar na metade esquerda. Ela só pode estar à direita.
• Atualização: low = mid + 1.
• A invariante é mantida porque agora sabemos que key > a[mid], então key deve estar no novo intervalo [mid+1, high].
• Caso 2 (a[mid] > key): O valor no meio é maior que a chave. A chave não pode estar na metade direita.
• Atualização: high = mid - 1.
• A invariante é mantida porque agora sabemos que key < a[mid], então key deve estar no novo intervalo [low, mid-1].

3. Conclusão

A invariante garante que o intervalo de busca [low, high] nunca exclui a posição onde a chave estaria, caso ela exista no array. Ao final do loop, se low > high, o intervalo está vazio, confirmando que a chave não foi encontrada.

A alternativa correta é aquela que expressa que a chave está compreendida entre os valores nas posições low e high. Na maioria das bancas examinadoras, a formulação correta refere-se ao intervalo fechado:

Portanto, a condição de invariância é:
a[low] \leq key \leq a[high]

Alternativa D.