Algoritmos #06 - Algoritmos de busca

Por Bruno Henrique - julho 27, 2019

Ao trabalharmos com estruturas de dados, como lista e vetores, pode haver casos em que seja necessário verificar se determinado elemento existe em uma sequência. Embora algumas linguagens já tragam funções pré-estabelecidas para realizar esta tarefa, é possível que, em certos casos, tal funcionalidade tenha que ser implementada pelo próprio programador. Diante disso, foram criados os chamados "algoritmos de busca/pesquisa", cujo funcionamento será explanado a seguir.

Busca sequencial

A Busca sequencial é o mais simples algoritmo de pesquisa existente, o qual pode ser utilizado em qualquer vetor. Seu funcionamento consiste basicamente em percorrer toda a sequência (da esquerda para a direita), comparar os elementos da sequência à variável desejada e, caso ela esteja presente lá, retornar "verdadeiro", caso contrário, o algoritmo retornará "falso".

Como na Busca sequencial existe a necessidade de que, no pior dos casos, todo o array seja percorrido, ela apresentará uma certa lentidão em vetores de tamanho grande e, portanto, não é indicada para tais situações.

- Exemplo de implementação em python:

Busca binária

Em razão dos problemas apresentados pela busca sequencial, surgiu a busca binária, um algoritmo consideravelmente mais eficiente e de mais difícil implementação, que utiliza do paradigma de "divisão e conquista" para varrer um vetor mais rapidamente. Para que a pesquisa binária funcione, é necessário que a sequência base esteja ordenada (em ordem alfabética ou crescente, por exemplo), por isso, é possível usar os algoritmos de ordenação, já apresentados no blog, antes da busca.

O algoritmo funciona da seguinte forma:

Escolhe-se o valor x (aquele será procurado na sequência);
Determina-se qual o elemento que está no meio da lista (m);
Caso x == m, a pesquisa acaba, pois, o valor foi encontrado.
Caso contrário:

Se x < m, o valor x deve estar à esquerda de m, na primeira metade da sequência (se ele existir). Agora a pesquisa será realizada apenas nessa parte da lista.
Se x > m, o valor x deve estar à direita de m, na segunda metade da sequência (se ele existir). Agora a pesquisa será realizada apenas nessa parte da lista.

O procedimento se repetirá até x seja encontrado ou a lista seja completamente percorrida. Como a lista é reduzida à metade em cada comparação, o tempo de busca é reduzido drasticamente.

- Exemplo de implementação em python: