Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / JavaScript

Pesquisa linear

A pesquisa linear verifica os elementos de um array por ordem até encontrar uma correspondência ou chegar ao fim. Não é necessário ordenar o array; a função apresentada devolve o índice da primeira correspondência ou -1.

Versão: ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support

Sintaxe

function linearSearch(array, target) {
  for (var i = 0; i < array.length; i++) {
    if (array[i] === target) return i;
  }
  return -1;
}

A pesquisa linear (linear search) é um algoritmo, não uma palavra-chave de JavaScript. Verifica os elementos sequencialmente, começando no índice 0, e termina na primeira correspondência. O array não precisa de estar ordenado. linearSearch(array, target) devolve o índice do elemento correspondente ou -1, mesmo quando o array está vazio.

O exemplo usa ===: não converte tipos, pelo que o número 8 não corresponde ao texto "8". NaN nem sequer corresponde a NaN, e os objetos só correspondem quando são o mesmo objeto. A função não altera o array. O exemplo pressupõe um array normal, sem posições vazias, que não é alterado durante a pesquisa.

Para n elementos, o pior caso exige n comparações: o tempo é O(n) e o espaço adicional é O(1), assumindo um custo constante para leituras e comparações. Uma correspondência imediata demora O(1). Verifique o resultado com index !== -1, não com if (index): o índice válido 0 é falsy, enquanto -1 é truthy.

O método integrado array.indexOf(target) também devolve o primeiro índice usando comparação estrita, mas ignora propriedades de índice em falta; o ciclo apresentado lê essas posições e normalmente obtém undefined. O algoritmo não pertence a uma edição específica do ECMAScript; o exemplo usa sintaxe disponível no ES3 e não precisa de Web APIs nem de métodos modernos de arrays.

Exemplos

function linearSearch(array, target) {
  for (var i = 0; i < array.length; i++) {
    if (array[i] === target) return i;
  }
  return -1;
}

var values = [8, 3, 8, 5];
console.log(linearSearch(values, 8));
console.log(linearSearch(values, 5));
console.log(linearSearch(values, 9));
console.log(linearSearch([], 8));

Resultado

0
3
-1
-1

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes