TOP 25 ALGORITMOS | Linear Search

Neste algoritmo, a iteração se realiza em todos os elementos do array verificando se o elemento atual é igual ao elemento alvo (chave). Se encontrarmos algum elemento igual ao elemento alvo, então retornamos o índice do elemento atual. Caso contrário, se nenhum elemento for igual ao elemento alvo, então retornamos -1, pois o elemento não foi encontrado.

// Javascript //

function search(array, n, x){
  for (let i = 0; i < n; i++)
      if (array[i] == x)
          return i;
  return -1;
}

🕰️ | Complexidade de Tempo

No melhor dos casos, a chave pode estar presente no primeiro índice, sendo portanto, equivalente a O(1). No pior dos casos, a chave pode estar presente no último índice, sendo portanto, equivalente a O(N).

📦 | Complexidade de Espaço

Como não há necessidade de utilização de outra variável a complexidade será de O(1).

✔️ | Vantagens

✦ Não requer memória adicional;

✦ Independe da organização do array;

✦ Independe do tipo de dados do array;

✦ Adequado para pequenos conjuntos de dados;

❌ | Desvantagens

✦ Inadequada para grandes conjuntos de dados;

📁 | Resumo