Repositório contendo estudos de algoritmos de busca desenvolvidos na linguagem C++.
Os algoritmos de busca presentes nesse repositório são aplicados sobre um vetor contendo elementos de uma classe denominada Individuo, contendo as variáveis int: id e idade; float: peso e altura; e string: nome.
class Individuo
{
private:
int id, idade;
float peso, altura;
string nome;Para mais informações sobre a classe e a estrutura dos dados verifique a pasta sobre Lista Sequencial Estática em meu repositório sobre Estruturas de Dados.
Todos os algoritmos buscam um Indivduo no vetor através de seu id.
O método utiliza uma variável int: id como parâmetro, assim como, um laço for que pode percorrer todo o vetor.
Individuo Lista::busca_linear(int id)
{
for (int i = 0; i < this->quantidade_max; i++)
{A cada etapa do laço o id do Individuo na posição i do vetor é comparado ao id recebido como parâmetro, assim que um Individuo com id idêntico ao recebido for encontrado o método é encerrado, retornando o mesmo.
if (this->lista[i].get_id() == id)
{
return this->lista[i];
}Caso o laço seja completado sem encontrar um Individuo com id idêntico ao recebido, o método é encerrado, retornando um Individuo: generico, inicializado pelo construtor padrão.
}
Individuo generico;
return generico;
}Melhor Caso: O(1)
Pior Caso: O(n)
O método utiliza uma variável int: id como parâmetro e uma variável Individuo: generico, inicializado pelo construtor padrão, assim como, um laço for que pode percorrer todo o vetor.
Individuo Lista::busca_ordenada(int id)
{
Individuo generico;
for (int i = 0; i < this->quantidade_max; i++)
{A cada etapa do laço o id do Individuo na posição i do vetor é comparado ao id recebido como parâmetro, assim que um Individuo com id idêntico ao recebido for encontrado o método é encerrado, retornando o mesmo.
if (this->lista[i].get_id() == id)
{
return this->lista[i];
}Caso contrário, é verificado se o id do Individuo na posição i do vetor é maior que o id recebido e em caso positivo, o método é encerrado, retornando a variável generico.
else if (this->lista[i].get_id() > id)
{
return generico;
}Caso o laço seja completado sem encontrar um Individuo com id idêntico ao recebido, o método é encerrado, retornando a variável generico.
}
return generico;
}Melhor Caso: O(1)
Pior Caso: O(n)
O método utiliza uma variável int: id como parâmetro, uma variável int: inicio, inicializada em 0, uma variável int: meio e uma variável int: fim, inicializada com o valor da variável quantidade_max menos 1, assim como um loop while que segue enquanto o valor da variável inicio for menor ou igual ao valor da variável fim.
Individuo Lista::busca_binaria(int id)
{
int inicio = 0;
int meio;
int fim = this->quantidade_max - 1;
while (inicio <= fim)
{A cada etapa do loop while a variável meio recebe o valor da média aritmética entre os valores das variáveis inicio e fim.
meio = (inicio + fim) / 2;Em seguida, é comparado o id do Individuo na posição correspondente ao valor da variável meio e o id recebido como parâmetro. Se o primeiro for maior, a variável fim recebe o valor da variável meio menos 1, limitando a pesquisa à primeira metade do vetor.
if (this->lista[meio].get_id() > id)
{
fim = meio - 1;
}Caso o primeiro seja menor, a variável inicio recebe o valor da variável meio mais 1, limitando a pesquisa à segunda metade do vetor.
else if (this->lista[meio].get_id() < id)
{
inicio = meio + 1;
}Caso os valores sejam iguais, o método é encerrado, retornando o Individuo armazenado na posição correspondente ao valor da variável meio.
else
{
return this->lista[meio];
}Caso o loop seja encerrado sem encontrar um Individuo com id idêntico ao recebido, o método é encerrado, retornando um Individuo: generico, inicializado pelo construtor padrão.
}
Individuo generico;
return generico;
}Melhor Caso: O(1)
Pior Caso: O(logn)
Os algoritmos apresentados nesse repositório partem de estudos iniciados no vídeo de busca em vetores do Dr. André Backes no canal Programação Descomplicada Linguagem C no YouTube.