busca sequencial vs binária

Prévia do material em texto

A busca sequencial ou busca linear , é o algoritmo mais simples de busca: Percorra a lista
comparando a chave com os valores dos elementos em cada uma das posições. Se a
chave for igual a algum dos elementos, retorna a posição correspondente na lista.
Exemplo de busca sequencial em java:
public int procura(Object[] vetor, Object elementoProcurado) {
int tamanhoVetor = vetor.length; /* o for, não precisa verificar o tamanho do vetor toda
vez que for comparar. */
for (int i = 0; i < tamanhoVetor; i++)
if (vetor[i].equals(elementoProcurado))
return i;
return -1; // Não achou, retorna -1
}
Já a busca binária é um eficiente algoritmo para encontrar um item em uma lista
ordenada de itens. Ela funciona dividindo repetidamente pela metade a porção da lista que
deve conter o item, até reduzir as localizações possíveis a apenas uma. é um algoritmo de
busca em vetores que segue o paradigma de divisão e conquista. Nós usamos a busca
binária em um jogo de adivinhação por exemplo, e um dos modos mais comuns de se usar
a busca binária é para encontrar um item em um array.
Exemplo de busca binária em pseudo-código:
USCA-BINÁRIA(V[], início, fim, e)
i recebe o índice do meio entre início e fim
se (v[i] = e) entao
devolva o índice i # elemento e encontrado
fimse
se (inicio = fim) entao
não encontrou o elemento procurado
senão
se (V[i] vem antes de e) então
faça a BUSCA-BINÁRIA(V, i+1, fim, e)
senão
faça a BUSCA-BINÁRIA(V, inicio, i-1, e)
fimse
fimse
Diferenças :
Principais diferenças entre pesquisa linear e pesquisa binária. A pesquisa linear é de
natureza iterativa e usa uma abordagem sequencial. Por outro lado, a pesquisa binária
implementa a abordagem de dividir e conquistar. A complexidade de tempo da pesquisa
linear é O (N), enquanto a pesquisa binária tem O (log 2 N). Ambos os algoritmos de
pesquisa linear e binária podem ser úteis dependendo da aplicação. Quando uma matriz é a
estrutura de dados e os elementos são organizados em ordem de classificação, a pesquisa
binária é preferida para pesquisa rápida . Se a lista vinculada for a estrutura de dados,
independentemente de como os elementos são organizados, a pesquisa linear é adotada
devido à indisponibilidade da implementação direta do algoritmo de pesquisa binária.
REFERÊNCIAS
https://pt.gadget-info.com/difference-between-linear-search#:~:text=Principais%20diferen%
C3%A7as%20entre%20pesquisa%20linear,O%20(log%202%20N).
https://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria
https://pt.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-s
earch