Linear Search

Qué es una búsqueda lineal o Linear Search

Linear Search o búsqueda lineal, es una búsqueda secuencial (de acuerdo a su Big O Notation). Compara elemento por elemento de un extremo a otro.

Supongamos que tenemos el siguiente arreglo de 15 elementos: [1, 3, 4, 7, 9, 11, 13, 16, 19, 18, 20, 22, 24, 27, 30]

• Necesitamos saber la posición del número 24 dentro del arreglo.

El algoritmo sería el siguiente:

1. Se inicializan un contador en 0 (primera posición del arreglo)
2. Si el elemento que está en la posición que indica el contador, terminamos nuestro ciclo.
3. Si no, incrementamos el contador en 1 y volvemos a revisar.

El valor sería encontrado en 13 iteraciones de nuestro algoritmo. Esto nos da una notación de tiempo de O (n), ya que pudo haberse recorrido todo el arreglo hasta encontrar el elemento. Este tipo de algoritmo es considerado in place, ya que no requiere estructura de dato adicional (otro arreglo) para encontrar el resultado.

var linearSearch = (lookUp) => {
  let numbers = [1, 3, 4, 7, 9, 11, 13, 16, 19, 18, 20, 22, 24, 27, 30];
  let count = 0;
  do {
    //Llevamos a cabo la comparación, si el elemento es encontrado,
    //terminamos nuestro ciclo
    if (numbers[count] === lookUp) {
      return 'Number ' + lookUp + ' found at position ' + count + ' in ' + (count+1) + ' iterations.';
    }
    //Contador de interaciones
    count++;
  } while(count<numbers.length);
  //No se encontró el elemento
  return 'Number ' + lookUp + ' not found';
};

console.log(linearSearch(24));

Aquí una liga con una buena referencia y amplia explicación de la búsqueda lineal.

Ver más algoritmos acá.