Considere o seguinte método binSearch() dessa classe: Efectua uma pesquisa binária por uma chave num array. Pré-condição: A array a[0]...a[length-1] está ordenada por ordem ascendente. Pós-condição: Devolve index tal que a[index] == key. Se key não está em v, então devolve -1. Suponha uma classe SomeClass onde está definida uma variável a[size] com os valores [4, 7, 9, 11, 20, 24, 30, 41]. O que é que ficará armazenado em y depois de executado o seguinte?

A questão apresenta um trecho de código em C++ que implementa um algoritmo de Busca Binária dentro de uma classe template. O objetivo é determinar o valor da variável y após a execução da função binSearch(4).

Resposta

O valor armazenado em y será 0.

Justificativa Didática

O algoritmo de Busca Binária funciona procurando um elemento-chave em um array ordenado dividindo repetidamente o intervalo de busca pela metade. Para entender o resultado, precisamos simular a execução passo a passo do método binSearch com a entrada key = 4.

Dados Iniciais:

• Array a: [4, 7, 9, 11, 20, 24, 30, 41]
• Comprimento (length): 8 (indices de 0 a 7)
• Chave (key): 4

Simulação do Código:

Detalhamento das Etapas:

1. Primeira Iteração:

• low = 0, high = 7
• Calcula-se o meio: mid = (0 + 7) / 2 = 3 (divisão inteira).
• Acessa-se a[3], que é o valor 11.
• Como 11 é maior que a chave 4, o algoritmo descarta a metade direita.
• Atualiza-se high = mid - 1, logo high = 2.

1. Segunda Iteração:

• low = 0, high = 2
• Calcula-se o meio: mid = (0 + 2) / 2 = 1.
• Acessa-se a[1], que é o valor 7.
• Como 7 ainda é maior que a chave 4, descarta-se a metade direita novamente.
• Atualiza-se high = mid - 1, logo high = 0.

1. Terceira Iteração:

• low = 0, high = 0
• Calcula-se o meio: mid = (0 + 0) / 2 = 0.
• Acessa-se a[0], que é o valor 4.
• A condição if (a[mid] == key) torna-se verdadeira (4 == 4).
• O comando return mid; executa, retornando o valor 0.

Portanto, a variável y receberá o índice encontrado no array, que é 0.