Busca linear

A busca linear é um algoritmo de força bruta não muito eficiente, mas com grande simplicidade, sendo utilizada regularmente por programadores.

Categoria de Programação

Postado em 04 setembro 2022

Atualizado em 04 setembro 2022

Palavras-chave: busca,linear,search,algoritmo,programacao,ciencia,computacao,informatica

Visualizações: 1282



A digitalização tem sido adotada como solução em muitos campos do mercado. Automóveis, eletrodomésticos e celulares recentes, geralmente possuem um computador embutido, trazendo muitas vantagens como integração com outros dispositivos, possibilitando a internet das coisas.

Essa digitalização exige mais programadores na área e estimula o campo de informática a evoluir em muitos aspectos. Hoje, diversas linguagens de programação estão disponíveis para implementação de sistemas, cada linguagem contém suas vantagens e são adequados para determinadas tarefas.

Por mais que as linguagens de programação tenham suas diferenças, processos de repetição (loops) certamente estão presentes em todas elas. Essas repetições são essenciais quando o assunto é sobre algoritmos. Quando falamos sobre algoritmos de repetição, sem dúvida a busca linear é o algoritmo mais comum.

O que é a busca linear na ciência da computação?

A busca linear, também chamada de busca sequencial é um algoritmo de força bruta, portanto não sendo considerado um algoritmo muito eficiente em alguns casos.

Esse algoritmo pesquisa cada elemento em uma estrutura de dados até encontrar o elemento procurado. Portanto, sendo linear e necessitando mais tempo de processo para chegar ao resultado final conforme os dados de entrada vão aumentando.

A busca linear é eficiente?

Se medirmos a eficiência da busca linear usando o método da notação do O grande teremos O(n), que na escala é classificado como “aceitável”.

Apesar de não ser um algoritmo tão eficiente é o mais fácil de implementar graças a sua simplicidade.

Quando utilizar a busca linear?

As máquinas recentes podem executar código com uma velocidade extremamente alta, portanto quando a quantidade de dados de entrada não é muito grande, o desempenho da máquina não muda significativamente.

A busca linear é um algoritmo simples que pode ser implementado rapidamente, agilizando o desenvolvimento de sistemas.

Quando não utiliza a busca linear?

Não é recomendável utilizar a busca linear quando a quantidade de dados é muito grande.

Por exemplo, quando há a necessidade de buscar determinados elementos em estrutura de dados contendo 30.000 linhas (records) de dados, outros algoritmos mais eficientes devem ser adotados, como a busca binária.

Como implementar a busca linear na prática?

A implementação de um algoritmo de busca linear simples necessita apenas de uma repetição e uma condição para ser estabelecida.

function elementoExiste(array $lista, string $elementoProcurado): boolean {
    // Repetição
    foreach ($lista as $linha) {
	    // Condição
	    if ($linha == $elementoProcurado) {
		    // Se elemento existir, retorna verdadeiro
		    return true;
	    }
    }
    
    // Se não existir o elemento na lista retorna falso
	return false;
}

// lista simples de frutas
$lista = [
    'maçã',
    'laranja',
    'melancia',
    'abacaxi'
];

// resultado: true
echo elementoExiste($lista, 'melancia');

busca linear algoritmo

Conclusão

A busca linear é um algoritmo de força bruta não muito eficiente, mas com grande simplicidade, sendo utilizada regularmente por programadores.

Conforme os dados de entrada ficam maiores, mais tempo de processamento será necessário para a busca linear chegar até o resultado.

Projetos práticos

Criando um jogo de pacman usando javascript e pixi.js (parte 1)

Desenvolvimento dos conceitos mais básicos do clássico pacman, como: mapa, animação, deslocamento e detector de colisões.

Criando artes de texto usando imagens

Convertendo imagens para ascii art usando o valor da intensidade das cores cinzentas.

Desenvolvendo o campo de visão de um personagem em um plano 2D

Detectando objetos que entram dentro do campo de visão do personagem. Útil para servir de "gatilho" para eventos em um jogo.

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.

Usando dados fornecidos pelo TSE para simular o gráfico das eleições presidenciais de 2022

Simulação dos gráficos do segundo turno das eleições presidenciais, utilizando python e ferramentas de análise de dados, pandas e jupyter.

Veja também

Os três pilares de segurança da informação são o requerimento mínimo para um serviço seguro

A quantidade de programadores só tende a aumentar com o tempo. Porém, muitos programadores ainda não conhecem os três pilares de segurança da informação.

Afinal, vale a pena gastar tempo com web marketing?

Expressões como gastar tempo e investir tempo andam lado a lado. Quando algo investido não tem o retorno esperado isso se torna uma perde de tempo...

Método scrum

Tem como objetivo entregar o projeto com velocidade e satisfazer as necessidades dos clientes entregando cada funcionalidade do software separadamente.

Machine Learning (Aprendizado de máquina)

Conjunto de algoritmos e técnicas que permitem que a máquina aprenda baseando-se em dados para realizar tarefas específicas.

Classes na programação

Conjunto de variáveis e funções que podem ser encapsuladas em uma única unidade de instância e definir o escopo e a acessibilidade de cada elemento

Seguir caminho (path following)

Um dos comportamentos de navegação (steering behaviors). Faz com que um agente siga um caminho pré-determinado pelo desenvolvedor.