Busca linear
Origem: Wikipédia, a enciclopédia livre.
Na área de informática, ou Ciência da Computação, costuma-se usar o termo busca linear 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.
Índice |
[editar] Análise de Complexidade
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/2 comparações. O algoritmo de busca linear é um algoritmo O(n).
[editar] Exemplo de código em C
/**
* 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;
}
[editar] Exemplo de código em Pascal
function procura(vetor :array [1..10] of integer; elementoProcurado: integer ; busca : boolean); {supondo que o vetor tem tamanho 10}
var
i : integer;
begin
busca:=false;
for i := 1 to 10 do
begin
if (vetor[i] = elementoProcurado) then
begin
procura := i; {retorna o índice do elemento procurado}
busca:=true; {para indicar que a busca encontrou o valor procurado no vetor}
end;
end;
end.
[editar] Fluxograma do Algoritmo
