6 Tipos de Algoritmos de Busca e Como Funcionam

Você pode imaginar algoritmos de busca como detetives digitais, encontrando o que você precisa em vastas coleções de dados, como sites ou bancos de dados, com o menor número de passos possível.

De Google e Amazon a Facebook e Netflix, algoritmos de busca desempenham um papel vital nas interações digitais do dia a dia.

Neste artigo, você aprenderá sobre os tipos mais comuns de algoritmos de busca, suas complexidades de tempo, como seus processos de busca funcionam e aplicações reais na ciência da computação.

A complexidade do caso médio mais baixa é melhor para um desempenho mais rápido, especialmente com entradas grandes. Algoritmos como busca binária O(log n) são altamente eficientes.

Por outro lado, complexidades mais altas, como O(n), podem se tornar impraticáveis para grandes conjuntos de dados devido ao crescimento linear ou pior do tempo de execução. No entanto, a eficiência também depende de fatores como estruturas de dados, contexto do problema, recursos e requisitos da aplicação.

1. Algoritmo de busca linear

Busca linear, também conhecida como busca sequencial, percorre cada elemento do array em um conjunto de dados sequencialmente, comparando-o com o elemento alvo até encontrar uma correspondência exata. Se a função de busca atingir o final do array sem encontrar uma correspondência, sinala que o elemento alvo não está presente no conjunto de dados.

O elemento alvo que você está procurando pode ser números, strings, objetos ou qualquer outro tipo de dado que possa ser armazenado em um array. Essa flexibilidade torna a busca linear um algoritmo versátil que pode ser aplicado a uma ampla gama de tipos de dados.

Para ilustrar melhor este processo de busca, vamos analisar um exemplo do mundo real.

Digamos que você tenha uma lista não ordenada de números inteiros representando as idades das pessoas em um grupo. Você é solicitado a descobrir se uma idade específica, digamos 25, está presente no array. Você começaria no início do array e verificaria cada elemento, um por um, até encontrar a idade 25 ou atingir o final do array.

O tempo de execução de um algoritmo de busca linear é proporcional ao tamanho do array. A complexidade computacional para busca linear é O(n), onde n é o número de elementos no array.

Aplicações de busca linear

• Tarefas de busca simples: A busca linear é frequentemente usada para um amplo espectro de tarefas de busca básicas em que o conjunto de dados é pequeno ou onde a complexidade adicional de outros algoritmos não é justificada. Por exemplo, procurar uma pequena lista de nomes ou números.
• Estruturas de dados lineares: A busca linear é fundamental para muitas estruturas de dados lineares como arrays, listas e pilhas. É tipicamente usada para varrer essas estruturas a fim de localizar elementos específicos ou realizar operações.
• Arrays não ordenados: Como a busca linear verifica cada elemento sequencialmente, ela pode localizar itens independentemente de suas posições no array.

2. Algoritmo de busca binária

Busca binária é um algoritmo eficiente usado para encontrar um valor alvo em uma lista ordenada. Ele divide repetidamente o intervalo de busca pela metade usando o método de busca binária. Em seguida, compara o valor alvo com o elemento do meio e procede para a parte direita ou esquerda do array. Este processo continua até que o valor alvo seja encontrado. Alternativamente, o intervalo de busca fica vazio quando o alvo não está presente no array.

Vamos analisar um exemplo de uso de busca binária para encontrar um valor numérico específico.

Imagine que você tenha um array de números: [2,5,8,12,16,23,38,56,72,91], e queira encontrar o número 23.

Você começa olhando para o elemento do meio (nó raiz), que é 16. Como 23 é maior que 16, você olha apenas para os números à direita de 16. Em seguida, você olha para o elemento do meio dessa parte, que é 56. Como 23 é menor que 56, você olha apenas para os números à esquerda de 56. Agora você olha para o elemento do meio novamente, que é 23. Você encontrou a chave de busca!

O tempo de execução de um algoritmo de busca binária é O (log n), onde n é o número de elementos no array.

Aplicações de busca binária

• Busca em bancos de dados: Este é um algoritmo eficaz para busca em banco de dados para localizar rapidamente registros com base em campos indexados, como IDs ou chaves.
• Encontrar elementos em arrays ordenados: A busca binária localiza eficientemente elementos em arrays ordenados, o que é útil em estruturas de dados baseadas em índice e aplicações como procurar uma palavra em um dicionário ou encontrar um item em uma lista ordenada.
• Fundação algorítmica: Serve como componente fundamental no desenvolvimento de algoritmos sofisticados de aprendizado de máquina. A busca binária ajuda no treinamento de redes neurais e na otimização de hiperparâmetros de modelo.
• Otimizando algoritmos: A busca binária é usada em algoritmos, incluindo estratégias de divisão e conquista, para resolver eficientemente problemas como encontrar raízes quadradas ou localizar elementos de pico em arrays.
• Busca em árvores: Árvores de busca binária (BSTs) usam este algoritmo para buscar, inserir e excluir elementos com eficiência, mantendo a ordem classificada da árvore.

3. Busca por interpolação

Quando valores em um array ordenado são distribuídos uniformemente, a busca por interpolação oferece uma vantagem sobre a busca binária. A interpolação envolve criar novos pontos de dados dentro do intervalo de espaço de busca conhecido.

Enquanto a busca binária sempre se concentra no elemento do meio, a busca por interpolação ajusta sua posição de busca com base no valor alvo sendo procurado. Por exemplo, se a chave de busca estiver mais próxima do final, a busca por interpolação tende a começar a procurar dados a partir desse final.

Para colocar isso em perspectiva, imagine que você está procurando um preço específico entre uma lista de preços de itens em uma loja. Esses preços estão organizados do mais baixo para o mais alto. Em vez de sempre verificar o meio da lista (como na busca binária), a busca por interpolação estima onde o preço pode cair com base em seu valor comparado aos preços mais baixos e mais altos. Em seguida, você repete esse processo até encontrar o preço.

O tempo de execução de um algoritmo de busca por interpolação é O(log log n), onde n é o número de elementos no array.

Aplicações de busca por interpolação

• Busca em bancos de dados: A busca por interpolação é comumente usada em bancos de dados para procurar registros com base em algum elemento-chave.
• Busca em grandes arrays: Este algoritmo de busca facilita uma busca mais eficiente em grandes arrays ordenados, especialmente quando a distribuição de valores é uniforme. Pode ser aplicado em vários campos, como computação científica, onde grandes conjuntos de dados precisam ser pesquisados com eficiência.
• Recuperação de dados de tabelas de símbolos: A busca por interpolação pode ser usada em tabelas de símbolos, onde chaves estão associadas a valores. Por exemplo, em linguagens de programação, as tabelas de símbolos são usadas para armazenar variáveis, funções e outros identificadores. A busca por interpolação pode localizar rapidamente as informações associadas a um identificador específico.
• Aplicações sensíveis ao tempo: Devido à sua capacidade de recuperar dados rapidamente, a busca por interpolação é adequada para aplicações sensíveis ao tempo.
• Tabelas hash: Eficiente para encontrar dados quando combinado com uma função hash.

4. Busca por saltos

Busca por saltos, também conhecida como busca em bloco, é especificamente projetada para arrays ordenados. Diferentemente da busca linear, que examina cada elemento sequencialmente, a busca por saltos avança em incrementos de tamanho fixo, ignorando vários elementos para buscas mais rápidas.

Se o elemento alvo estiver em um intervalo especificado, o algoritmo emprega uma busca linear dentro desse bloco. Esta abordagem reduz substancialmente as operações, melhorando a eficiência da busca.

Vamos analisar um exemplo do algoritmo de busca por saltos.

Imagine que você está tentando encontrar um número específico em uma longa lista de números e quer fazer isso mais rapidamente do que verificar cada número um por um.

1. Decida quantos números pular cada vez que você procura: Digamos que você pulará 3 números por vez.
2. Comece a procurar pela lista, pulando adiante pela quantidade escolhida cada vez, até encontrar um número igual ou maior que o que você está procurando.
3. Depois de encontrar um intervalo onde o número pode estar, execute uma busca linear até encontrar o alvo.

O tempo de execução de um algoritmo de busca por saltos é O(√n), onde n é o número de elementos no array ordenado.

Aplicações de busca por saltos

• Aplicações JavaScript: A busca por saltos otimiza o processo de busca em aplicações JavaScript, melhorando a eficiência e a responsividade.
• Busca em sistemas de banco de dados: Este algoritmo procura registros com base em algum elemento-chave em grandes bancos de dados.
• Recuperação de dados de mídia visual: A busca por saltos localiza eficientemente um quadro específico em um grande arquivo de vídeo avançando um número fixo de quadros por vez.

5. Busca exponencial

O algoritmo de busca exponencial, também conhecido como busca de duplicação ou galope, difere da busca por saltos na forma como divide o array e no tipo de busca empregada dentro dessas divisões. Enquanto a busca por saltos divide o array em blocos e usa busca linear, a busca exponencial divide o array usando potências exponenciais de 2 e aplica busca binária.

Essencialmente, a função de busca atravessa exponencialmente todo o array, da esquerda para a direita, segmentando-o em blocos menores usando potências de 2. O algoritmo realiza uma busca binária dentro de cada um desses blocos até encontrar o alvo.

Como esse algoritmo de busca pode ser um pouco complexo, vamos ilustrar seu funcionamento aplicando-o a um cenário real.

Imagine que você tenha uma prateleira de livros classificados alfabeticamente por título. Você está procurando um livro específico, digamos “Harry Potter e a Pedra Filosofal.” Em vez de procurar em cada livro um por um, você decide usar a busca exponencial.

Eis como funciona:

1. Ponto de partida: Você começa com o primeiro livro no lado esquerdo da sua prateleira. Se este não for o livro que você procura, prossiga.
2. Mova-se para a direita, dobrando sua janela de busca: Se você encontrar “Harry Potter e a Pedra Filosofal” em uma dessas posições, você encontrou seu livro.
3. Repita o processo: Você continua repetindo o processo, dobrando o intervalo a cada vez, até encontrar o livro.

Ambora não seja a aplicação exata da busca exponencial, este exemplo ajuda a demonstrar como você pode localizar rapidamente o livro sem a necessidade de passar por cada livro um por um.

O tempo de execução de um algoritmo de busca exponencial é O(log n), onde n é o número de elementos no array classificado.

Aplicações da busca exponencial

• Encontrando dados em grandes arrays classificados: A busca exponencial encontra rapidamente elementos em grandes arrays classificados, como listagens de produtos, estendendo exponencialmente o intervalo de busca, ideal para situações em que a busca linear é muito lenta.
• Procurando sistemas de arquivos: Este algoritmo melhora as buscas de sistema de arquivos encontrando rapidamente arquivos ou diretórios dentro de estruturas de diretório através da expansão exponencial do intervalo de busca.

6. Busca ternária

Busca ternária é um algoritmo de busca projetado para determinar a posição de um valor alvo em um array classificado. Ao contrário da busca binária, que divide o array em duas partes, a busca ternária o divide em três. Ao comparar o valor alvo com elementos em dois pontos e dividir o array em três partes, a função de busca reduz eficientemente o espaço de busca.

Para ilustrar um exemplo, vamos aplicar a busca ternária para encontrar o número 6 no array [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

• Divida a área de busca:
  • Divida sua área de busca em três partes encontrando dois pontos de divisão: Um ponto está em torno de um terço do caminho a partir da esquerda (digamos 4), e o outro está em torno de dois terços a partir da esquerda (digamos 8).
  • Isso divide a área em [1, 4], (5, 8) e [9, 10].
• Compare com o alvo:
  • Verifique se o número que estamos procurando (6) é igual a 4 ou 8.
  • Não é igual a 4 ou 8, então você ajusta seus apontadores com base em onde 6 pode estar localizado:
    • Como 6 é maior que 4 mas menor que 8, movemos o apontador esquerdo para 5 e o apontador direito para 7.
• Repita ou conclua:
  • Continue repetindo este processo com o espaço de busca reduzido até encontrar o número 6 ou não ter mais área para buscar.
  • Eventualmente, você reduz a área de busca para [6, 6] e encontra o número que estava procurando!

O tempo de execução de um algoritmo de busca ternária é O(log3 n), onde n é o número de elementos no array classificado.

Aplicações da busca ternária

• Funções unimodais: A busca ternária é aplicada em funções unimodais para identificar seus valores máximos ou mínimos. Funções unimodais são aquelas que têm um único valor máximo.

Conclusão

As aplicações de diferentes tipos de algoritmos de busca são vastas e diversas, abrangendo desde buscas em grandes bancos de dados, ajudando a otimizar aplicações, até servir como blocos de construção para o desenvolvimento de algoritmos avançados de aprendizado de máquina para busca.

Ao manter em mente as complexidades de tempo e espaço, capacidades, combinadas com as vantagens e desvantagens de cada um dos algoritmos mencionados, você pode tomar decisões informadas. Seja em uma atribuição de aula de ciência da computação, ou quando estiver desenvolvendo o próximo aplicativo revolucionário, dominando técnicas como busca binária, DFS, BFS e divisão e conquista, você pode desbloquear todo o potencial de estruturas de dados e melhorar o desempenho do seu sistema.

Se você estiver construindo ou avaliando busca para uma loja online especificamente, a mecânica funciona um pouco diferente na prática. Veja como a busca de e-commerce funciona nos bastidores.

Perguntas frequentes