Algoritmos de busca são comuns em programas, já que muitas vezes tais programas incluem a funcionalidade de permitir a realização de pesquisas sobre os dados sendo manipulados. Porém, quando a quantidade de dados é muito grande, torna-se necessário uma avaliação de qual técnica de busca vai ser utilizada, pois essa decisão irá impactar diretamente no desempenho do programa.
Leia a questão abaixo e tente respondê-la. Se não conseguir, não se preocupe, estudaremos os conceitos necessários para compreendê-la logo a seguir.
Assista às aulas abaixo, ministradas pelo professor da universidade de Harvard Patrick Schmid.
Vídeo 1:
Vídeo 2:
Agora vamos responder a questão:
Inicialmente vamos eliminar alguns itens:
- Descartamos a letra “c”, já que os itens devem estar organizados na forma binária (vista no vídeo 2);
- A letra “d” esta incorreta, pois os elementos não precisam estar ordenados para a busca sequencial ocorrer (contra exemplo visto no vídeo 1);
- Por último, descartamos a letra “e”, porque a busca sequencial acaba quando encontramos a chave.
Agora reduzimos nosso problema para duas afirmações, a letra a e a letra b.
Analisando esses dois itens, eliminamos a letra a. Já que o tempo do algoritmo é O(log n) para o tempo médio.
Assim a letra “b” é a correta, pois realmente, no pior caso, a pesquisa binária percorre "log de n na base 2" elementos em sua execução.
Para entender melhor a resposta da questão resolvida acima, execute o algoritmo em um exemplo simples de tamanho 8, colocando a chave procurada em uma das folhas da arvore binária, e observe o que acontece. Ou calcule a complexidade da busca binária (apresentada no vídeo 2) para o pior caso.
Referências:
Grupo PET Computação UFCG, 2013. All rights reserved.
