Esse site utiliza cookies
Nós armazenamos dados temporariamente para melhorar a sua experiência de navegação e recomendar conteúdo do seu interesse.
Ao utilizar os nossos serviços, você concorda com as nossas políticas de privacidade.
Esse site utiliza cookies
Nós armazenamos dados temporariamente para melhorar a sua experiência de navegação e recomendar conteúdo do seu interesse.
Ao utilizar os nossos serviços, você concorda com as nossas políticas de privacidade.
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.
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.
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.
A imagem acima apresenta o nível de processamento necessário conforme os dados de entrada aumentam.
A busca binária tradicional usa 3 variáveis:
Responsável por armazenar o índice mais baixo da lista. Geralmente inicia-se com o número zero.
Armazena o valor da lista contendo o índice mais alto. Geralmente inicia-se com o número de itens dentro da lista.
Resultado da soma do mínimo e máximo, divido pelo número 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'
];
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.
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:
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”.
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);
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
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 programa que encontra a menor distância entre dois pontos dentro de um labirinto usando o algoritmo A* (a-estrela).
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.
Usando lógicas matemáticas como trigonometria para criar e calcular o esqueleto de um jogo de tiro 2D em javascript
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.
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
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 é a abreviação de Low Power Wide Area. LPWA é um modo de comunicação wireless entre dispositivos. É principalmente utilizado em dispositivos IoT.
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.
Interface dedicada ao desenvolvedor ou especialista da computação para executar comandos ao computador sem a presença de um mouse.
Também conhecida como quarta revolução industrial, utiliza tecnologias modernas para automatizar processos. Iniciou-se em 2011, na Alemanha.