---
tags: Lab_ICC_II
---
<center>
<h3>
Universidade de São Paulo (USP)<br>
Instituto de Ciências Matemáticas e de Computação (ICMC)<br>
</h3>
<h3>
Bacharelado de Ciências de Computação<br>
Disciplina: Laboratório de Introdução à Ciência da Computação II<br>
Professor: Leonardo Pereira<br><br>
Aluno: Guilherme Machado Rios (11222839)
</h3>
<h1>
Análise informal de algoritmos de buscas
</h1>
</center>

## Introdução

Serão feitas as análises de três algoritmos envolvendo busca em um vetor de inteiros previamente ordenado. O primeiro é uma simples busca sequencial, o segundo e terceiro uma busca binária, iterativa e recursiva, respectivamente.

## Qual é mais eficiente? Por quê?

Em um contexto genêrico (vetor gerado randomicamente) pode-se dizer que a busca binária, em suas duas implementações, é mais eficiente — mesmo que, em certos casos, haja a nececissadade de ordenação do vetor de entrada — dado que uma busca desse tipo trabalha com a ideia de ***divisão e conquista***. Procurando um elemento sempre ao meio de um vetor ordenado, o algoritmo conseque ***dividir*** esse vetor e, caso o elemento não se encontre no meio, ***conquistar***, analisando em qual metade esse elemento está, o subvetor do qual o procurado faz parte; com o mesmo se repetindo para esse subvetor, de forma iterativa ou recursiva.
Vale ressaltar que a busca binária implementada iterativamente, quando comparada a implementação recursiva, pode se mostrar mais efiente. O tratamento de memória é melhor naquela, pois nessa um espaço além é ocupado pelas chamadas recursivas que vão sendo empilhadas.

Concluindo, pressupondo a escolha de um bom algoritmo que garanta a ordenação do vetor no qual ocorrerá a busca, ***buscas binárias se mostram mais efientes, na média, para vetores significamente grandes***. Sendo assim, *buscas sequencias podem ser mais adequadas a contextos com vetores menores*.

## Em que caso(s) o algoritmo apresenta sua melhor performance?

1. *`sequential_search()`:* chave 8867 da entrada `4.in`, dado que essa é a chave mais próxima do ponto de partida da busca, o início do vetor;

2. *`iterative_bin_search()`:* a chave 218439197 da entrada `1.in`, dado que essa está mais próxima do início da lista de "pontos médios" no contexto de divisão e conquista, entre as listas de todas as entrada;

3. *`recursive_bin_search()`:* a chave 329090 da entrada `3.in`, seguindo a mesma lógica utilizada acima para a busca iterativa.

## Em que caso(s) (entrada) o algoritmo apresenta sua pior performance (pior caso)?
1. *`sequential_search()`:* chave 598893067 da entrada `4.in`, dado que essa é a chave mais distante do ponto de partida da busca, o início do vetor;

2. *`iterative_bin_search()`:* a chave 0 da entrada `4.in`, já que essa não está no vetor, o que culmina na execução do número máximo de iterações para esta função; além disso, esse é o maior vetor de todos nos quais a chave não é encontrada;

3. *`recursive_bin_search()`:* as chaves 34 e 623309823 da entrada `3.in`, seguindo a mesma lógica utilizada acima para a busca iterativa.