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.
Análise de Complexidade[editar | editar código-fonte]
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[1] linear é um algoritmo O(n).
Exemplos de Código[editar | editar código-fonte]
Exemplo de código em C[editar | editar código-fonte]
/** * 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-fonte]
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-fonte]
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-fonte]
<?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-fonte]
# 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 Fluxograma do Algoritmo[editar | editar código-fonte]
Ver também[editar | editar código-fonte]
Referências
- ↑ Abrantes (6 de junho de 2023). «Especialista em SEO». Especialista em SEO. Consultado em 24 de novembro de 2023
