Busca linear

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Na área de informática, ou Ciência da Computação, costuma-se usar o termo busca linear (ou busca sequêncial) 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/2 comparações. O algoritmo de busca 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 ; busca : boolean): 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) {
     for (int i = 0; i < vetor.length; 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));
 
?>

Fluxograma do Algoritmo[editar | editar código-fonte]

Busca sequencial.png

Ver também[editar | editar código-fonte]

Ícone de esboço Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.