<Direto ao Ponto 59> Algoritmos de busca

Artigos desta série: ( < ) Anterior | Índice | Seguinte ( > )

Olá, dev!

Este é mais um artigo da série DIRETO AO PONTO, que eu estou escrevendo para a DIO. Ele vai tratar de algoritmos de busca (ou de pesquisa), usados em muitos programas que codificamos, como os de ordenação também, tratados no artigo anterior.

Sumário

1.   Introdução

2.  Os algoritmos de busca

3.  Complexidade dos algoritmos de busca

4.  Considerações finais

5.  Referências

1 – Introdução

Eu criei a série de artigos DIRETO AO PONTO com o objetivo de apresentar, de forma simples e direta, conhecimentos básicos da programação e de computação, principalmente, para os iniciantes.

Aqui, são tratados temas como lógica de programação, linguagens, hardware dos computadores, história da computação e assuntos relacionados à plataforma da DIO, como a escrita de artigos e os desafios de código.

Neste artigo, serão tratados os algoritmos de busca. Junto com os algoritmos de ordenação, eles são usados por muitos programas com o objetivo de buscar dados que estão armazenados nas mais diversas estruturas de dados.

As buscas se tornam mais eficientes quando os dados já estão ordenados, então, operações de ordenação e de busca caminham juntas.

Existem vários algoritmos de busca disponíveis, cada um com suas características próprias, alguns mais adequados para determinados tipos de aplicações do que outros.

Além disso, eles apresentam diferentes tipos de complexidade. Para uma aplicação específica, entre vários algoritmos possíveis para a implementação, é importante escolher aquele com menor complexidade de tempo ou de espaço de memória.

2 – Os algoritmos de busca

Um algoritmo de busca é uma técnica usada para encontrar um valor ou uma informação específica em uma estrutura de dados. Os principais tipos de algoritmos de busca variam em termos de complexidade, velocidade e uso de memória, e podem ser categorizados como buscas lineares e buscas binárias, entre outras variações destas duas.

A seguir, são descritos os principais tipos de algoritmos de busca, com exemplos de códigos em Python.

Busca Linear (“Linear Search”) - Percorre a lista elemento por elemento até encontrar o valor desejado ou até chegar ao fim da lista. É a abordagem mais simples, tendo complexidade O(n).

Como funciona?

O algoritmo percorre uma lista elemento por elemento, comparando cada um com o valor que se está procurando, até encontrá-lo ou até chegar ao fim da lista. Veja o algoritmo a seguir:

1.   Inicia no primeiro elemento da lista.

2.   Compara o valor atual com o valor procurado.

3.   Se o valor for igual ao procurado, retorna a posição do elemento.

4.   Se não for, continua para o próximo elemento.

5.   Se percorrer toda a lista sem encontrar o valor, retorna uma indicação de que o valor não está presente (geralmente -1).

Ver a figura abaixo:

Exemplo em Python:

# Função de busca 
def linear_search(arr, target):
 for i in range(len(arr)):
     if arr[i] == target:
         return i
 return -1
 
 
# Exemplo de uso
import random
arr = random.sample(range(1, 101), 100)  # Lista NÃO ORDENADA
target = 85
index = linear_search(arr, target)
print(f"Elemento {target} encontrado no índice {index}")

Busca Binária (“Binary Search”) - Aplicada em listas ordenadas, ela funciona dividindo repetidamente a lista ao meio e comparando o elemento central com o valor buscado. Dependendo do resultado da comparação, descarta metade da lista a cada iteração. Sua complexidade é O(log n).

Como funciona?

O princípio da busca binária é dividir a lista em duas partes a cada passo, descartando a metade onde o valor não pode estar. Veja o algoritmo:

1.   Verifique o elemento do meio da lista;

2.   Se o elemento do meio for igual ao valor procurado, retorne a sua posição;

3.   Se o valor procurado for menor que o elemento do meio, repita a busca na metade esquerda da lista;

4.   Se o valor procurado for maior que o elemento do meio, repita a busca na metade direita da lista;

5.   Continue dividindo até encontrar o valor ou até restar uma lista vazia, indicando que o valor não está presente;

6.   Se resultar em uma lista vazia, retorna uma indicação de que o valor não está presente (geralmente -1).

Os extremos de cada sublista considerada na busca são definidos por variáveis que indicam os índices do lado esquerda, direito e o do meio da sublista.

A cada consulta, há a redefinição destas variáveis para se adequarem à nova sublista que será considerada (ver a figura abaixo).

Exemplo em Python:

# Função de busca 
def binary_search(arr, target):
 low = 0
 high = len(arr) - 1
 
 while low <= high:
 mid = (low + high) // 2
 if arr[mid] == target:
   return mid
 elif arr[mid] < target:
   low = mid + 1
 else:
   high = mid - 1
 return -1
 
# Exemplo de uso
import random
arr = sorted(random.sample(range(1, 101), 100))  # Lista ORDENADA
target = 85
index = binary_search(arr, target)
print(f"Elemento {target} encontrado no índice {index}")

Além destes dois tipos básicos, existem algumas variações destes, como a Busca Interpolada e a Busca Exponencial, com alguns ganhos em situações específicas.

3 – Complexidade dos algoritmos de busca

Gráfico com a comparação das diversas complexidades envolvidas para os dois algoritmos:

Agora veja uma tabela comparativa para os casos de algoritmos tratados aqui:

Resumindo, a busca linear pode ser aplicada em listas ordenadas ou desordenadas, mas ela é ineficiente para listas grandes, já que pode ser necessário percorrer toda a lista. A busca binária é muito eficiente para listas grandes e ordenadas. No entanto, ela só funciona em listas ordenadas.

4 – Considerações finais

Este é mais um artigo da série DIRETO AO PONTO, que eu estou escrevendo para a DIO.

Desta vez, foram apresentadas as principais técnicas de busca (ou de pesquisa), que são a busca linear e a busca binária.

Um algoritmo de busca é uma técnica usada para encontrar uma informação específica em uma estrutura de dados.

Elas são mais eficientes quando os dados já estão ordenados, por isso as operações de busca e de ordenação são complementares.

Foram apresentados os conceitos básicos envolvidos com as duas técnicas, seus funcionamentos, e exemplos de códigos para suas implementações em Python.

Em resumo, a busca linear é simples e direta, mas ineficiente para listas grandes, enquanto a busca binária é muito eficiente, mas exige que a lista esteja ordenada.

No próximo artigo, encerarei o tema de algoritmos, mostrando como um mesmo algoritmo pode ser usado para implementar códigos em várias linguagens diferentes.

5 – Referências

Praticamente todo o conteúdo deste artigo foi tirado do que eu aprendi (e me lembro) sobre o assunto desde o início da minha carreira como programador, desde os anos 80 até agora.

Os códigos em Python foram consultados no ChatGPT. Depois, eles foram atualizados por mim e foram executados com sucesso.

Artigos desta série: ( < ) Anterior | Índice | Seguinte ( > )