Busca-struzik

Busca Exponencial (também chamado busca a galope ou busca Struzik).

É um algoritmo, criado por Jon Bentley e Andrew Chi-Chih Yao em 1976, para a buscar listas ordenadas ilimitadas.

Tópicos

• Sobre o algoritmo de busca exponencial
• Como executar o código
• Busca binária
• Busca Exponencial
• Complexidade da busca exponencial.
• Aplicabilidade
• Referências

Sobre o algoritmo de busca exponencial

• A pesquisa exponencial permite pesquisar em uma lista classificada e ilimitada por um valor de entrada especificado. O algoritmo consiste em duas etapas, por isso que a busca exponencial é considerada um algoritmo híbrido. A primeira fase visa buscar um intervalo de um array de entrada no qual assume-se que o elemento desejado deve estar presente e, estando o elemento no intervalo, aplica-se a segunda etapa, que seria realizar uma busca binária nesse intervalo pequeno.

Como executar o código

• Para a execução do código é preciso abrir o terminal e digitar ./main

gcc -c busca_struzik.c
gcc -c main.c
gcc -o main busca_struzik.o main.o

Busca binária

• Para utilizar a pesquisa exponencial é preciso ter conhecimento da busca binária (ou busca sequencial/linear, mas esta, em comparação com a binária é menos eficiente). No código implementamos uma função de busca binária:

int buscaBinaria(Aluno *alunos, int inicio, int fim, char *valor);

Busca exponencial

int buscaExponencial(Aluno *alunos, int tamanho, char *valor);

A função receberá um ponteiro do tipo Aluno que aponta para uma struct, um int tamanho que receberá o número de alunos cadastrados(tamanho total do array) e um ponteiro de char que passará o nome pesquisado. Dentro da função iniciaremos uma variávei index com 1, pois o salto começa no primeiro índice do array. Pesquisa o intervalo dentro do qual o nome está incluído, aumentando o índice em potências de 2 Se este intervalo existir no array apliqua o algoritmo de Pesquisa Binária sobre ele, caso contrário, retorna -1.

Complexidade de busca exponencial

Tempo:

T(n) = C1 + C2 + C3 + C4(log n) + C5 (log n) + C6 +C7 + C8
T(n) = a + log n(b)
T(n) = a + log nb

1 -> T(n) = a + log nb //Remove Constantes de soma
2 -> T(n) = log nb //Remove Constantes Multiplicativas
3 -> T(n) = log n
T(n) = O(log n) //Notaçao Big O da Busca Exponencial 

Espaço:

A complexidade de espaço é definida por O(1), pois espaço usado é constante, i = 1.

Aplicabilidade

• Sua aplicabilidade se destaca principalmente em cenários onde o custo de acesso aos elementos é alto ou quando estamos lidando com listas muito grandes.
• Exemplo:
  Lista de nomes ordenados
  busca de nome por ou ID
  busca de aluno por nome ou matricula.

Referências

Algoritmo de Ordenação: Comparação de Desempenho | by Ismaelly Eyre | Medium https://medium.com/@ismaelly_eyre_/algoritmos-de-ordenação-comparação-de-desempenho-e23806adab2f
Quicksort - Wikipédia, a enciclopédia livre https://pt.wikipedia.org/wiki/Quicksort
Busca Exponencial - Wikipédia, a enciclopédia livre https://pt.wikipedia.org/wiki/Busca_exponencial
Andrew Chi-Chih Yao - Wikipédia, a enciclopédia livre https://pt.wikipedia.org/wiki/Andrew_Chi-Chih_Yao
Jon Bentley - Wikipédia, a enciclopédia livre https://pt.wikipedia.org/wiki/Jon_Bentley