Busca binária

A busca binária usa o método de divisão de conquista que visa em dividir os problemas em pequenos problemas até que eles se resolvam sozinhos.

Categoria de Programação

Postado em 22 setembro 2022

Atualizado em 22 setembro 2022

Palavras-chave: busca,binaria,linear,notacao,grande,o,problema,solucao,programacao,algoritmo,tecnica,metodo

Visualizações: 974



Métodos de aprimoração de algoritmo tem sido desenvolvidos ao longo da história da programação. Hoje, por mais que uma máquina seja poderosa, ela pode ser influenciada pelas técnicas de algoritmo.

Em algumas ocasiões onde um grande volume de dados de entrada tem que ser processados, determinadas técnicas de algoritmo devem ser implementadas.

Um bom exemplo é uma função de busca. Alguns sistemas possuem milhares de registros no banco de dados. Portanto, procurar registro por registro pode ser prejudicial para a experiência do usuário. Nesse caso, uma boa técnica a ser implementada é a busca binária.

O que é a busca binária na programação?

A busca binária é uma técnica de algoritmo de busca de algum dado específico dentro de uma lista.

Essa técnica visa em dividir a lista pela metade até encontrar o elemento de busca. Eliminando elementos desnecessários, etapas desnecessárias também serão eliminadas, consequentemente melhorando o desempenho do algoritmo.

Porém, a lista precisa estar em ordem para funcionar de modo legítimo. Portanto, listas fora de ordem não irão ter suas buscas efetivamente efetuadas.

Por que usar a busca binária?

Adotando a busca binária pode-se melhorar a velocidade dos métodos de busca. Diferente de técnicas como busca linear, também conhecido por “algoritmo de força bruta”, a busca binária elimina elementos que podem ser ignorados.

Utilizando um meio de medição como a notação do grande O, a busca binária pode ser classificada como O(logn), isso quer dizer que o desempenho da busca binária pode ser classificada como excelente.

Mesmo em cenários onde volumosos dados de entrada são processados, a busca binária não apresenta grandes custos de processamento, exigindo menos da máquina e melhorando a experiência do usuário.
comparação busca linear e binaria
A imagem acima apresenta o nível de processamento necessário conforme os dados de entrada aumentam.

Como a busca binária funciona?

A busca binária tradicional usa 3 variáveis:

  • Mínimo (min)
  • Máximo (max)
  • Adivinhação (guess)

Variável mínimo (min)

Responsável por armazenar o índice mais baixo da lista. Geralmente inicia-se com o número zero.

Variável máximo (max)

Armazena o valor da lista contendo o índice mais alto. Geralmente inicia-se com o número de itens dentro da lista.

Adivinhação (guess)

Resultado da soma do mínimo e máximo, divido pelo número 2:

guess=(min+max)/2; guess= (min+max)/2;

Lembrando que essa variável representa o índice e não o valor de cada registro da lista.

// Valor: alfabeto
// Índice: número
$list = [
    0 => 'a',
    1 => 'b',
    2 => 'c'
];

Método de divisão de conquista

A busca binária usa o método de divisão de conquista que visa em dividir os problemas até que eles se resolvam sozinhos.

busca binária

Como é o fluxograma da busca binária?

O processo repete-se enquanto a variável “máximo” continua maior do que a variável “mínimo”.

Em cada repetição, a variável “adivinhação” irá possuir o resultado.

Caso esse resultado seja maior do que o elemento de busca, esse resultado irá ser utilizado para sobrepor a variável “máximo”. Caso o resultado seja menor do que o elemento de busca, a variável “mínimo” irá ser sobreposta pelo resultado e terá o número um somado:

Condição Sobrepõe
Resultado == Busca -
Resultado > Busca Máximo = Resultado - 1
Resultado < Busca Mínimo = Resultado + 1

A representação do algoritmo de busca binária pode ser representada pelo fluxograma abaixo:
fluxograma busca binária

Por que busca binária tem esse nome?

O termo “busca binária” vem do inglês “binary search”. Tem esse nome pelo fato de dividir a lista em dois pedaços em cada repetição, usando duas variáveis, “min” e “max”.

Como usar a busca binária na prática?

A implementação da busca binária na prática pode ser escrito com o algoritmo abaixo:

function doBinarySearch($search, $array) {
    $min = 0;
    $max = count($array);
    
    while ($min <= $max) {
        $guess = floor(($min + $max) / 2);
        
        if ($array[$guess] == $search) {
            return $guess;
        }
        
        if ($array[$guess] > $neddle) {
            $max = $guess - 1;
        } else {
            $min = $guess + 1;
        }
        
    }
    
    return null;
}

Usando uma lista, a função acima retornará os seguintes resultados:

$list = [1,2,3,6,8,10,12,15,20,21,22,25,30,37,38,39,40,42,45,48,51,55,57,61,64,67,68,70,71,72,73,74,75,76,77,78,79,80,85,90,91,92,93,94,95,96,97,99];

// retorna 0
echo doBinarySearch(1, $list);

// retorna 47
echo doBinarySearch(99, $list);

// retorna 23
echo doBinarySearch(61, $list);

// retorna nulo
echo doBinarySearch(9, $list);

Conclusão

A busca pode ser uma boa alternativa para substituir algoritmos de força bruta, graças a sua simplicidade e efetividade. Esse método utiliza técnica de divisão e conquista, onde o problema é dividido em pequenos problemas até que se resolva sozinho.

Para funcionar de modo correto, a busca binária necessita que os items da lista estejam em ordem.

Projetos práticos

Integrando o PHP com Elasticsearch no desenvolvimento de um sistema de busca

Projeto de criação de um sistema de busca usando o framework Symfony e Elasticsearch. A integração com Kibana também é feito de modo remoto com um raspberrypi.

Implementando um algoritmo de pathfinding

Implementando um programa que encontra a menor distância entre dois pontos dentro de um labirinto usando o algoritmo A* (a-estrela).

Integrando Laravel com o protocolo MQTT para comunicação entre dispositivos

Projeto de comunicação entre dois dispositivos ESP8266 e Raspberrypi4. Laravel irá funcionar como servidor e receptor de dados de temperatura e umidade coletados com o DHT11.

Criando o esqueleto de um jogo de tiro 2D visto de cima usando P5.js

Usando lógicas matemáticas como trigonometria para criar e calcular o esqueleto de um jogo de tiro 2D em javascript

Criando um sistema de integração contínua (CI/CD)

Fazendo a integração contínua de Jenkins, Sonatype Nexus, Sonatype, JUnit e Gradle para automatizar processos repetitivos. Prática bastante usada em tecnologias de DevOps.

Veja também

O endereçamento de dispositivos na internet é automatizado graças ao DHCP

Antigamente o endereçamento de dispositivos era feito manualmente, porém isso traz muitas dificuldades em questão de administração. O DHCP resolve esses problemas

Todo empreendedor deve estar consciente que cada funcionário é um humano, portanto deve reconhecer as tentações em alguns cenários

Estudar o comportamento das pessoas pode auxiliar um administrador a criar um sistema de fiscalização mais eficiente, evitando fraudes que prejudicam a imagem da empresa

LPWA Low Power Wide Area

LPWA é a abreviação de Low Power Wide Area. LPWA é um modo de comunicação wireless entre dispositivos. É principalmente utilizado em dispositivos IoT.

Triângulo da fraude

O triângulo da fraude tenta explicar o motivo que levou uma pessoa a cometer uma fraude usando como base a pressão, a oportunidade e a justificação.

Terminal

Interface dedicada ao desenvolvedor ou especialista da computação para executar comandos ao computador sem a presença de um mouse.

Indústria 4.0

Também conhecida como quarta revolução industrial, utiliza tecnologias modernas para automatizar processos. Iniciou-se em 2011, na Alemanha.