Question

Considere o array = {1, 9, 15, 20, 55, 70, 89, 96}.
Quantas comparações são necessárias para encontrar o valor 96, caso seja utilizado o método de pesquisa binária? Descreva os passos utilizados para obter sua resposta.

Answer 1

Resposta:

3

Explicação:

A complexida de da busca binária é O(log(n)), onde n é o tamanho do array onde vc quer realizar a busca. No nosso caso, o tamanho é 8. Logo log(8) = 3

O algoritmo é bem simples. Supondo que vc tem 2 ponteiros "esq" e "dir":

esq = 0

dir = array.size()

while (esq < dir):

   meio = (esq + dir) / 2 # Tenha certeza que essa divisão seja um inteiro.

   if(array[meio] == 96):

        return 96

   if (array[meio] < 96):

       esq = meio + 1

  else:

      dir = meio

return error

Então, seguindo o mesmo:

meio = 55 -> (0 + 8) / 2 = 4

55 < 96: dir = meio

meio = 89 -> (4 + 8) / 2 = 6

89 < 96: dir = meio

meio = 96

96 == 96 (achou)