Busca Binária e Sequencial: Entenda os principais Algoritmos de busca
O problema da busca em um vetor de elementos é um problema clássico da Ciência da Computação, ele possui basicamente duas soluções bem conhecidas, a busca binária e a busca sequencial. Entender esses dois algoritmos é algo crucial para a formação de um bom profissional de desenvolvimento de software.
Nesse artigo vamos passar pela definição do problema, e apresentação das duas soluções mencionadas, análise dos algoritmos, além de alguns exemplos de implementação e casos de uso práticos.
Problema da busca em um vetor
Um dos problemas mais clássicos em computação, é o da busca de um elemento em um conjunto de dados. Todo estudante de computação se depara com ele no início, e todo desenvolvedor, iniciante ou experiente se depara com ele constantemente no dia a dia. Portanto entender todos os cenários possíveis, e soluções existentes em cada um deles, é essencial para um profissional de qualidade.
Esse problema possui diversas formas de apresentação, o conjunto de dados estar em memória ou em disco, os dados estarem ordenados ou não, possuírem elementos repetidos ou não, estarem indexados ou não, e assim por diante.
A forma mais básica, e que serve como ponto de partida para solução de todas as outras, é termos um conjunto de dados em memória em uma estrutura indexada, ou seja, um vetor ou array de elementos.
Então, de maneira geral, o problema da busca em vetor consiste em: Dado um vetor de elementos de um determinado tipo, e um outro elemento do mesmo tipo, identificar se o elemento está contido ou não no vetor, e em qual posição.
Algumas questões em plataformas de problemas online que envolvem o problema da busca:
Busca Sequencial – Solução intuitiva
A solução mais básica e intuitiva para o problema da busca em um vetor, é simplesmente percorrer cada elemento do vetor, comparando com o elemento que estamos buscando.
Essa solução é chamada de “Busca Sequencial”. O código abaixo demonstra uma implementação desse algoritmo em C:
int search(int* arr, int elem, int size)
{
int i;
for (i = 0; i < size; i++) {
if (arr[i] == elem) {
return i;
}
}
return -1;
}A maior vantagem do algoritmo da busca sequencial, é a sua simplicidade para implementação, conforme pode ser visto no código acima. O algoritmo consiste basicamente numa repetição para checar cada um dos elementos do array e comparar com o elemento buscado.
O algoritmo possui uma complexidade de tempo linear O(n), ou seja, o tempo necessário para encontrar o elemento cresce na mesma medida que o tamanho do vetor de entrada cresce.
Esse comportamento não é um problema para entradas pequenas, mas em cenários onde temos um vetor com muitos elementos, ou precisamos fazer muitas buscas consecutivas no mesmo vetor, o algoritmo acaba não tendo um bom desempenho.
Pontos positivos da busca sequencial
- Algoritmo intuitivo e de simples implementação;
- Funciona em qualquer estrutura de dados;
- Não exige processamento prévio dos dados da lista;
- Funciona independente da ordem de disposição dos elementos na lista;
- Eficiente para cenários onde tempos uma lista pequena de elementos;
Pontos negativos da busca sequencial
- Desempenho ruim em listas grandes;
- Não se aproveita de condições específicas da disposição dos elementos, como o caso do vetor estar ordenado;
Busca Binária – Uma solução mais eficiente
Uma solução mais eficiente para os cenários comentados anteriormente, onde o vetor de entrada possui muitos elementos, é o algoritmo da busca binária. A limitação desse algoritmo é que o vetor de entrada precisa estar ordenado para que ele funcione.
A busca binária é um algoritmo eficiente para resolver o problema da busca em um vetor ordenado de elementos, diferente da busca sequencial que checa todos os elementos do vetor, a busca binária consegue a cada checagem, descartar metade dos elementos do vetor, reduzindo a complexidade para uma ordem logarítimica.
Como Funciona a Busca Binária
- Pré-requisito:
- A lista deve estar ordenada. Sem isso, a busca binária não funciona corretamente.
- Passos do Algoritmo:
- Determine o elemento do meio da lista.
- Compare o valor desejado com o valor do meio:
- Se for igual, o elemento foi encontrado.
- Se for menor, o elemento deve estar na metade inferior da lista (esquerda).
- Se for maior, o elemento deve estar na metade superior da lista (direita).
- Repita o processo na metade restante.
- Continue até encontrar o elemento ou até que o espaço de busca se torne vazio.
Abaixo temos uma implementação do algoritmo de busca binária em C:
int binarySearch(int* arr, int elem, int size)
{
int inf = 0;
int sup = size - 1;
while (inf <= sup) {
int mid = inf + (sup - inf) / 2;
if (arr[mid] == elem) {
return mid;
}
if (arr[mid] < elem) {
inf = mid + 1;
} else {
sup = mid - 1;
}
}
return -1;
}A definição do espaço de busca do momento, é feito através das variáveis inf e sup que funcionam como limites inferior e superior da lista.
O elemento central, é calculado em função de inf e sup, e o descarte de uma das metades da lista é feito nas linhas 14 e 16, jogando os limites para após ou antes o elemento verificado no momento.
Abaixo é possível observar o comportamento do algoritmo ao buscar um elemento dentro de um vetor:
Complexidade da Busca Binária
Uma das razões para a popularidade da busca binária é sua eficiência. A cada iteração ou chamada recursiva, o tamanho do intervalo de busca é reduzido pela metade.
- Melhor Caso: O(1), ocorre quando o elemento procurado é encontrado logo na primeira tentativa.
- Pior Caso: O(log n), ocorre quando é necessário dividir o intervalo várias vezes até encontrar o elemento ou concluir que ele não está presente.
- Caso Médio: O(log n), semelhante ao pior caso em cenários práticos.
Comparada à busca linear, que tem complexidade O(n), a busca binária é muito mais eficiente em listas grandes. O gráfico abaixo demonstra a diferença entre um algoritmo O(n) e um algortimo O(log n)
Pontos positivos da busca binária
- Alta Eficiência: Reduz drasticamente o número de comparações em listas grandes.
- Simplicidade: Embora a lógica seja um pouco mais complexa que a busca linear, sua implementação é relativamente simples.
- Aplicação em Estruturas de Dados Ordenadas: É ideal para arrays, listas ordenadas e árvores binárias.
Pontos negativos da busca binária
- Requisito de Ordenação: A busca binária só funciona em listas previamente ordenadas. Caso contrário, será necessário ordenar a lista antes, o que pode aumentar o custo computacional.
- Maior Complexidade Inicial: A lógica pode ser mais difícil de entender para iniciantes comparada à busca sequencial.
- Inflexibilidade: Só funciona em estruturas de dados que permitam acesso direto, como vetores. Em listas encadeadas ou estruturas semelhantes, não é possível utilizar a busca binária.
Aplicações Práticas
A busca binária tem inúmeras aplicações em ciência da computação, estatística, e áreas relacionadas:
- Sistemas de Banco de Dados: Para buscar registros em índices ordenados.
- Pesquisa em Arquivos: Como em livros digitais e sistemas de busca.
- Problemas de Algoritmos Competitivos: Muitos problemas de otimização utilizam a busca binária como uma abordagem eficiente, como os problemas citados no início do artigo.
Conclusão
O problema da busca em uma lista de elementos é um dos principais problemas clássicos de computação, e é importante para qualquer profissional entender suas características, e os principais algoritmos que o resolvem.
Mesmo com as linguagens atuais possuindo funções já prontas, que resolvem esse problema, internamente, essas funções vão invariavelmente utilizar a implementação de algum desses algoritmos. Dessa forma, é importante que você entenda como eles funcionam, pra saber qual função usar, quando usar, e até mesmo se faz mais sentido implementar a sua própria função de busca, otimizando para a situação.
A busca binária é um algoritmo fundamental em ciência da computação, destacando-se por sua eficiência em listas ordenadas. Embora tenha limitações, suas vantagens tornam-no indispensável em muitas aplicações. Compreender como implementá-lo e adaptá-lo a diferentes problemas é uma habilidade essencial para qualquer programador.
Seja você um iniciante ou um desenvolvedor experiente, dominar a busca binária trará benefícios práticos para resolver problemas complexos de maneira elegante e eficiente.
Bacharel em Ciência da Computação pela Universidade Federal do Amazonas, MBA em Gerenciamento de Projetos pela Fundação Getúlio Vargas.
Atualmente trabalha como Gerente de Engenharia na Meliuz.
Com 20 anos de experiência na área, já trabalhou com um pouco de tudo, C, C++, Java, C#, Delphi, Node.js, AWS, PHP, Python, React, Angular, jQuery, e mais um monte de coisa que nem existe mais 😀
