Comparaciones
Coincidencias
Por revisar

  • Valor buscado
  • Comparadas
  • Descartadas
  • Encontradas

Más sobre la búsqueda lineal

Búsqueda lineal

La búsqueda lineal es la forma más sencilla de encontrar un valor: empezar por el principio y revisar cada valor por turno hasta que aparezca. Funciona con cualquier lista, ordenada o no. Elige el valor que buscar, reproduce la búsqueda o avanza de comparación en comparación, y observa cómo el coste depende de dónde está el valor, o de si está siquiera. Pulsa Reproducir para ver la búsqueda, o Paso y Atrás para avanzar de comparación en comparación. Arrastra el control de pasos para saltar a cualquier punto. La línea discontinua marca el valor buscado. Elige el valor, cuántas barras hay, cómo empiezan, o escribe tus propios números. Desactiva «Parar en la primera coincidencia» para encontrar todas las coincidencias. Con el tablero seleccionado, las flechas avanzan paso a paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.

Cómo funciona

  1. Elige el valor que buscar, cuántas barras hay y cómo empiezan. O escribe tus propios números.
  2. Pulsa Reproducir, o usa Paso y Atrás para avanzar de comparación en comparación. Arrastra el control de pasos para saltar a cualquier punto de la búsqueda.
  3. Desactiva «Parar en la primera coincidencia» para revisar cada valor y encontrar todas las coincidencias.

Cómo funciona la búsqueda lineal

Compara el primer valor con el valor buscado. Si son iguales, has terminado. Si no, pasa al segundo valor, luego al tercero, y así sucesivamente. Si llegas al final de la lista sin una coincidencia, el valor buscado no está en la lista. No hay nada que preparar: la lista no tiene que estar ordenada.

Cuántas comparaciones

Un valor en la posición k se encuentra tras k comparaciones. El mejor caso es una comparación, cuando el valor buscado es el primero. El peor caso es n, cuando es el último o no está, porque solo después de revisar cada valor puedes estar seguro de que no está. De media, para un valor que está en la lista, hacen falta unas (n + 1)/2. Con una lista ordenada, la búsqueda binaria lo hace mucho mejor: unas log₂ n comparaciones, 6 en lugar de hasta 40 para 40 valores.

Preguntas frecuentes

¿Cómo funciona la búsqueda lineal?

Revisa los valores de una lista uno a uno, del primero al último, hasta encontrar el valor buscado o quedarse sin valores. También se llama búsqueda secuencial.

¿Cuál es la complejidad temporal de la búsqueda lineal?

O(n): en el peor caso, cuando el valor buscado es el último o no está, lo compara con los n valores. De media, para un valor que está en la lista, hacen falta unas (n + 1)/2 comparaciones.

¿Cuándo conviene la búsqueda lineal?

Para listas cortas, para listas sin ordenar en las que solo se busca una o dos veces, y para datos que solo se pueden leer en orden, como un flujo. Ordenar primero para poder usar la búsqueda binaria solo compensa si buscas muchas veces.

¿Por qué un valor ausente cuesta más?

Porque nada le indica a la búsqueda lineal que pare antes. Una coincidencia solo se puede descartar revisando cada valor, así que un valor que no está en la lista siempre cuesta n comparaciones.

¿Se envían mis números a algún sitio?

No. La búsqueda se ejecuta en tu navegador, y tus últimos ajustes se quedan en el almacenamiento local de este navegador.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Ir al editor