Comparaciones
Aún posibles
La búsqueda lineal necesitaría

  • Valor buscado
  • Aún posibles
  • Comparadas
  • Descartadas
  • Encontradas

Más sobre la búsqueda binaria

Búsqueda binaria

La búsqueda binaria encuentra un valor en una lista ordenada mirando siempre en el centro. Si el valor central es demasiado pequeño, el objetivo solo puede estar después; si es demasiado grande, solo antes. En ambos casos se descarta la mitad de lo que queda. Elige el valor que buscar, avanza por la búsqueda paso a paso y mira cómo la parte sombreada se reduce hasta encontrar el objetivo o hasta que no queda nada. Pulsa Reproducir para ver la búsqueda, o Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto. La línea discontinua marca el valor que buscas, y la parte sombreada muestra dónde puede estar todavía. La búsqueda binaria necesita una lista ordenada, así que una lista desordenada se ordena primero. Elige el valor, cuántas barras hay, o escribe tus propios números. 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 y cuántas barras hay. O escribe tus propios números: la búsqueda binaria los ordena primero.
  2. Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto de la búsqueda.
  3. Compara el recuadro Comparaciones con «La búsqueda lineal necesitaría», para un valor cerca del final o uno que falte.

Cómo funciona la búsqueda binaria

Ten presente la parte de la lista ordenada que aún puede contener el objetivo; al principio es toda la lista. Mira el valor en su centro. Si es igual al objetivo, has terminado. Si es menor, el objetivo solo puede estar después, así que sigue con la parte posterior al centro. Si es mayor, sigue con la parte anterior. Cuando no queda nada, el objetivo no está en la lista.

Por qué es tan rápida

Cada comparación reduce a la mitad la parte que queda. Partiendo de n valores, tras k comparaciones quedan como máximo unos n/2ᵏ, así que la búsqueda termina tras ⌊log₂ n⌋ + 1 comparaciones como máximo: 6 para 40 valores, 10 para 1000, 20 para un millón. La búsqueda lineal puede tener que mirar todos los valores. El inconveniente es que la lista debe estar ordenada, y mantenerla ordenada, u ordenarla antes, tiene su propio coste.

Preguntas frecuentes

¿Cómo funciona la búsqueda binaria?

Compara el objetivo con el valor central de la parte de una lista ordenada que aún puede contenerlo. Si son iguales, lo ha encontrado; si no, descarta la mitad que no puede contener el objetivo y sigue en la otra mitad hasta encontrarlo o hasta que no queda nada.

¿Cuántas comparaciones necesita la búsqueda binaria?

Como máximo ⌊log₂ n⌋ + 1 para una lista de n valores: 6 para 40, 10 para 1000, 20 para un millón. Cada comparación reduce a la mitad lo que queda.

¿Por qué la búsqueda binaria necesita una lista ordenada?

Porque solo en una lista ordenada una comparación te dice en qué lado está el objetivo. En una lista desordenada, un valor menor en el centro no dice nada sobre dónde está el objetivo, así que no se puede descartar nada.

¿Qué valor encuentra si hay duplicados?

Cualquiera de ellos, según dónde caigan los centros. Las variantes que siguen buscando a la izquierda o a la derecha tras una coincidencia encuentran la primera o la última aparición.

¿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