Busca linear
Na área de informática, ou Ciência da Computação, costuma-se usar o termo busca linear (ou busca sequencial) para expressar um tipo de pesquisa em vetores ou listas de modo sequencial, i. e., elemento por elemento, de modo que a função do tempo em relação ao número de elementos é linear, ou seja, cresce proporcionalmente. Num vetor ordenado, essa não é a pesquisa mais eficiente, a pesquisa (ou busca) binária, por exemplo, é um tipo de pesquisa com o gráfico de tempo logarítmo.
Na área de informática, ou Ciência da Computação, costuma-se usar o termo busca linear (ou busca sequencial) para expressar um tipo de pesquisa em vetores ou listas de modo sequencial, i. e., elemento por elemento, de modo que a função do tempo em relação ao número de elementos é linear, ou seja, cresce proporcionalmente. Num vetor ordenado, essa não é a pesquisa mais eficiente, a pesquisa (ou busca) binária, por exemplo, é um tipo de pesquisa com o gráfico de tempo logarítmo.
Análise de Complexidade
[editar | editar código]No melhor caso, o elemento a ser buscado é encontrado logo na primeira tentativa da busca. No pior caso, o elemento a ser buscado encontra-se na última posição e são feitas N comparações, sendo N o número total de elementos. No caso médio, o elemento é encontrado após (N+1)/2 comparações. O algoritmo de busca linear é um algoritmo O(n).
Exemplos de Código
[editar | editar código]Exemplo de código em C
[editar | editar código]/**
* Retorna -1 caso não encontre ou a posição, caso encontre.
*/
int procura(char vetor[], int tamanho, char elementoProcurado) {
int i;
for (i = 0; i < tamanho; i++) {
if (vetor[i] == elementoProcurado) {
return i;
}
}
return -1;
}
Exemplo de código em Pascal
[editar | editar código]function procura(vetor :array [1..10] of integer; elementoProcurado: integer ): Integer; {supondo que o vetor tem tamanho 10}
var
i : integer;
retorno: integer;
begin
retorno := -1;
for i := 1 to 10 do
begin
if (vetor[i] = elementoProcurado) then
begin
retorno := i; {retorna o índice do elemento procurado}
break;
end;
end;
procura := retorno;
end.
Exemplo de código em Java
[editar | editar código] public int procura(Object[] vetor, Object elementoProcurado) {
int tamanhoVetor = vetor.length; /* o for, não precisa verificar o tamanho do vetor toda
vez que for comparar. */
for (int i = 0; i < tamanhoVetor; i++)
if (vetor[i].equals(elementoProcurado))
return i;
return -1; // Não achou, retorna -1
}
Exemplo de código em PHP
[editar | editar código]<?php
/**
* Retorna -1 caso não encontre ou a posição
* caso encontre.
*/
function buscaSequencial($elementoProcurado, array $vetor) {
$tamanhoVetor = count($vetor);
for ($i = 0; $i < $tamanhoVetor; $i++) {
if ($vetor[$i] == $elementoProcurado) {
return $i;
}
}
return -1;
}
$a = array(1, 2, 3, 4, 5, 6);
print "<br /> buscaSequencial(4, [1, 2, 3, 4, 5, 6]); return: "; var_dump(buscaSequencial(4, $a));
print "<br /> buscaSequencial(6, [1, 2, 3, 4, 5, 6]); return: "; var_dump(buscaSequencial(6, $a));
print "<br /> buscaSequencial(1, [1, 2, 3, 4, 5, 6]); return: "; var_dump(buscaSequencial(1, $a));
print "<br /> buscaSequencial(8, [1, 2, 3, 4, 5, 6]); return: "; var_dump(buscaSequencial(8, $a));
?>
Exemplo de código em Python
[editar | editar código]# Retorna None caso não encontre ou a posição, caso encontre.
def procura(lista, elemento):
assert isinstance(lista, list)
for indice in range(len(lista)):
if lista[indice] == elemento:
return indice
else:
return None
Exemplo de código em JavaScript
[editar | editar código]function buscaSequencial (dados, chave) {
for (var i = 0; i < dados.length; i ++){
if (dados[i] === chave) return i;
}
return -1;
}
const array = [5, 4, 8, 1, 2, 6, 7, 3];
const valorProcurado = 6;
const resultado = buscaSequencial(array, valorProcurado);
if (resultado !== -1) {
console.log(`Valor ${valorProcurado} encontrado na posição ${resultado}.`);
} else {
console.log(`Valor ${valorProcurado} não encontrado no vetor.`);
}
Fluxograma do Algoritmo
[editar | editar código]
