ALGORITIMOS DE BUSCA

Prévia do material em texto

ADS – ANALISE E DESENVOLVIMENTO DE SISTEMAS 
ESTRUTURAS DE DADOS 
 
 
 
 
 
 
 
OMAR BELCHIOR GAIDO 
 
 
 
 
 
 
 
 
ALGORITMOS DE BUSCA NA COMPUTAÇÃO 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Caxias – MA 
2021 
HISTÓRIA 
Os algoritmos de busca têm como base o método de procura de qualquer 
elemento dentro de um conjunto de elementos com determinadas propriedades. 
Que podiam ser livros nas bibliotecas, ou dados cifrados, usados principalmente 
durante as duas grandes guerras. Seus formatos em linguagem 
computacional vieram a se desenvolver juntamente com a construção dos 
primeiros computadores. Sendo que a maioria de suas publicações conhecidas 
começa a surgir a partir da década de 1970. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
https://pt.wikipedia.org/wiki/Cifra
https://pt.wikipedia.org/wiki/Guerra_mundial
https://pt.wikipedia.org/wiki/Linguagem_de_computador
https://pt.wikipedia.org/wiki/Linguagem_de_computador
https://pt.wikipedia.org/w/index.php?title=Computar_eletr%C3%B4nico&action=edit&redlink=1
DEFINIÇÃO DE ALGORITMO DE BUSCA 
Em ciência da computação, um algoritmo de busca, em termos gerais é 
um algoritmo que toma um problema como entrada e retorna a solução para o 
problema, geralmente após resolver um número possível de soluções. 
Uma solução, no aspecto de função intermediária, é um método o qual um 
algoritmo externo, ou mais abrangente, utilizará para solucionar um determinado 
problema. Esta solução é representada por elementos de um espaço de 
busca, definido por uma fórmula matemática ou um procedimento, tal como 
as raízes de uma equação com números inteiros variáveis, ou uma combinação 
dos dois, como os circuitos hamiltonianos de um grafo. 
Já pelo aspecto de uma estrutura de dados, sendo o modelo de 
explanação inicial do assunto, a busca é um algoritmo projetado para encontrar 
um item com propriedades especificadas em uma coleção de itens. Os itens 
podem ser armazenadas individualmente, como registros em um banco de 
dados. 
A maioria dos algoritmos estudados por cientistas da computação que 
resolvem problemas são algoritmos de busca. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
https://pt.wikipedia.org/wiki/Ci%C3%AAncia_da_computa%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/Algoritmo
https://pt.wikipedia.org/wiki/Entrada
https://pt.wikipedia.org/w/index.php?title=Otimiza%C3%A7%C3%A3o_matem%C3%A1tica&action=edit&redlink=1
https://pt.wikipedia.org/w/index.php?title=Otimiza%C3%A7%C3%A3o_matem%C3%A1tica&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Raiz_(matem%C3%A1tica)
https://pt.wikipedia.org/wiki/Equa%C3%A7%C3%A3o_diofantina
https://pt.wikipedia.org/wiki/Inteiros
https://pt.wikipedia.org/wiki/Vari%C3%A1vel_(matem%C3%A1tica)
https://pt.wikipedia.org/w/index.php?title=Cirucito_de_Hamilton&action=edit&redlink=1
https://pt.wikipedia.org/wiki/Teoria_dos_grafos
https://pt.wikipedia.org/wiki/Cole%C3%A7%C3%A3o
https://pt.wikipedia.org/wiki/Registro_(ci%C3%AAncia_da_computa%C3%A7%C3%A3o)
https://pt.wikipedia.org/wiki/Banco_de_dados
https://pt.wikipedia.org/wiki/Banco_de_dados
ALGORITMOS DE BUSCA 
Busca sequencial 
• É o método de pesquisa mais simples que existe. 
• Funcionamento: 
o a partir do primeiro registro, pesquise sequencialmente até 
encontrar o valor procurado ou até chegar ao fim do vetor; 
o então pare. 
Exemplo de Busca sequencial 
• valor buscado: 6 
 
5 1 4 6 0 
• deve-se comparar o primeiro, segundo terceiro valor com o 
valor buscado sucessivamente até encontrar uma 
igualdade. 
 
5 1 4 6 0 
• 5==6? 
 
5 1 4 6 0 
• 1==6? 
 
5 1 4 6 0 
• 4==6? 
 
5 1 4 6 0 
• 6==6? 
• E assim o valor é encontrado sequencialmente. 
Algoritmo de busca sequencial 
bool busca_sequencial(int v[], int n, int procurado){ 
for(int i = 0; i < n; i++){ 
if(v[i] == procurado){ 
return true; 
} 
} 
return false; 
} 
Busca binaria 
• Método de busca eficiente para um vetor ordenado 
• Esse método é semelhante ao que usávamos para procurar uma 
palavra no dicionário, por exemplo. 
• Funcionamento: 
o Compare o elemento procurado com o elemento que está 
na posição do meio do vetor: 
▪ Se o elemento foi encontrado, termine a busca. 
▪ Se o elemento procurado é menor do que o elemento 
do meio, repita a busca para a primeira metade do 
vetor. 
▪ Se o elemento procurado é maior do que o elemento 
do meio, repita a busca para a segunda metade do 
vetor. 
o Esse processo se repete até que o elemento seja 
encontrado ou até que todo vetor tenha sido consultado sem 
sucesso 
Exemplo de busca binária 
• valor buscado: 6 
 
0 1 4 5 6 
esq meio dir 
• deve-se buscar primeiramente no elemento que está no 
meio do vetor. 
 
0 1 2 3 4 
0 1 4 5 6 
esq meio dir 
• como nesse exemplo o elemento procurado é maior que o 
elemento do meio, o próximo passo é repetir a busca na 
segunda metade do vetor. 
 
 
0 1 2 3 4 
0 1 4 5 6 
 meio dir 
• deve-se buscar novamente o elemento que está no meio, 
porém agora considerando apenas os elementos da 
segunda metade. 
 
0 1 2 3 4 
0 1 4 5 6 
 dir 
• desta forma o valor é encontrado pelo método de busca 
binária. 
• Se o elemento procurado estiver ou não no vetor, a busca 
binária apresenta resultado melhores do que a busca 
sequencial. 
• Porém, é preciso manter o vetor ordenado (alto custo 
computacional). 
• Adequada quando a quantidade de consultas realizadas é 
bem maior do que a quantidade de inserções feitas no 
conjunto de elementos. 
Algoritmo de busca binária 
bool busca_binária(int v[], int n, int procurado){ 
int esq = 0, dir = n-1, meio; 
while(esq <= dir){ 
meio = (esq+dir)/2; 
if(v[meio] == procurado) 
return true; 
else if(v[meio] > procurado) 
dir = meio-1; 
else esq = meio+1; 
} 
return false; 
} 
 
 
 
 
 
 
REFERENCIAS 
 
Algoritmos para pesquisa e ordenação Disponível em: 
https://pt.scribd.com/document/378404253/308-358 
 
Algoritmos de Busca Comparação de Algoritmos Disponível em: 
http://www.decom.ufop.br/romildo/2019-2/bcc702/Aula17-Busca-
Comparacao-de-Algoritmos.pdf 
 
Algoritmos e programação de computadores Disponível em: 
https://ic.unicamp.br/~mc102/aulas/aula11.pdf 
 
https://pt.scribd.com/document/378404253/308-358
http://www.decom.ufop.br/romildo/2019-2/bcc702/Aula17-Busca-Comparacao-de-Algoritmos.pdf
http://www.decom.ufop.br/romildo/2019-2/bcc702/Aula17-Busca-Comparacao-de-Algoritmos.pdf
https://ic.unicamp.br/~mc102/aulas/aula11.pdf