Busca linear

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');

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.