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. [caption id="attachment_7320" align="aligncenter" width="652"]Linear Search Linear Search[/caption] [pastacode lang="javascript" manual="var%20linearSearch%20%3D%20(lookUp)%20%3D%3E%20%7B%0A%20%20let%20numbers%20%3D%20%5B1%2C%203%2C%204%2C%207%2C%209%2C%2011%2C%2013%2C%2016%2C%2019%2C%2018%2C%2020%2C%2022%2C%2024%2C%2027%2C%2030%5D%3B%0A%20%20let%20count%20%3D%200%3B%0A%20%20do%20%7B%0A%20%20%20%20%2F%2FLlevamos%20a%20cabo%20la%20comparaci%C3%B3n%2C%20si%20el%20elemento%20es%20encontrado%2C%0A%20%20%20%20%2F%2Fterminamos%20nuestro%20ciclo%0A%20%20%20%20if%20(numbers%5Bcount%5D%20%3D%3D%3D%20lookUp)%20%7B%0A%20%20%20%20%20%20return%20'Number%20'%20%2B%20lookUp%20%2B%20'%20found%20at%20position%20'%20%2B%20count%20%2B%20'%20in%20'%20%2B%20(count%2B1)%20%2B%20'%20iterations.'%3B%0A%20%20%20%20%7D%0A%20%20%20%20%2F%2FContador%20de%20interaciones%0A%20%20%20%20count%2B%2B%3B%0A%20%20%7D%20while(count%3Cnumbers.length)%3B%0A%20%20%2F%2FNo%20se%20encontr%C3%B3%20el%20elemento%0A%20%20return%20'Number%20'%20%2B%20lookUp%20%2B%20'%20not%20found'%3B%0A%7D%3B%0A%0Aconsole.log(linearSearch(24))%3B" message="Búsqueda Lineal" highlight="7,14" provider="manual"/] Aquí una liga con una buena referencia y amplia explicación de la búsqueda lineal. Ver más algoritmos acá.
Note to VCs: Aviada is not for sale. Please look somewhere else.