Hilera de cajas numeradas con una lupa partiendo la fila por la mitad, ilustrando la búsqueda binaria frente a la lineal

Búsqueda lineal vs binaria: el poder de partir por la mitad

· ⏱ 8+ min lectura

Buscar: el problema de cada día

Seguimos con la serie de Algoritmos, y empezamos a usar de verdad lo que aprendimos a medir con la notación Big-O. El primer problema al que se la aplicamos es el más común de todos: buscar algo dentro de una colección.

Parece tonto, pero buscar está en todas partes. ¿Está este usuario en la lista? ¿En qué posición está este producto? ¿Existe este valor? Y, como casi todo en programación, se puede hacer a lo bestia o con cabeza. Hoy vemos las dos formas, y la diferencia entre ellas es de las que te dejan con la boca abierta.

Búsqueda lineal: mirar uno a uno

La búsqueda lineal es la forma natural, la que harías sin pensar. Empiezas por el principio y vas mirando elemento por elemento hasta encontrar el que buscas (o hasta llegar al final y rendirte).

FUNCION busqueda_lineal(lista, objetivo)
  PARA i DESDE 0 HASTA longitud(lista) - 1
    SI lista[i] == objetivo ENTONCES
      RETORNAR i        // lo encontré, devuelvo su posición
    FIN SI
  FIN PARA
  RETORNAR -1           // no está
FIN FUNCION

Simple, honesta y funciona siempre, esté la lista ordenada o no. Esa es su gran virtud. ¿Su problema? La velocidad. En el peor caso (que el elemento no esté, o esté el último) tienes que mirar todos los elementos. Si hay n elementos, son n comprobaciones. Eso es O(n), lineal: el doble de datos, el doble de trabajo.

Para una lista de diez elementos, da igual. Para una de diez millones, empieza a doler.

Búsqueda binaria: partir por la mitad

Aquí viene la magia, y es la misma que usas tú sin darte cuenta al buscar una palabra en un diccionario de papel: no empiezas por la A, abres por el medio.

La búsqueda binaria funciona así: miras el elemento del centro. Si es el que buscas, listo. Si tu objetivo es menor, sabes que está en la mitad de la izquierda, así que tiras la mitad derecha entera a la basura. Si es mayor, al revés. Y repites con la mitad que queda. Cada paso descarta la mitad de lo que queda por mirar.

FUNCION busqueda_binaria(lista, objetivo)
  inicio = 0
  fin = longitud(lista) - 1

  MIENTRAS inicio <= fin
    medio = (inicio + fin) / 2     // división entera
    SI lista[medio] == objetivo ENTONCES
      RETORNAR medio
    SI NO SI lista[medio] < objetivo ENTONCES
      inicio = medio + 1           // descarto la mitad izquierda
    SI NO
      fin = medio - 1              // descarto la mitad derecha
    FIN SI
  FIN MIENTRAS

  RETORNAR -1
FIN FUNCION

El requisito imprescindible

La búsqueda binaria tiene una condición que no es negociable: la colección tiene que estar ordenada. Toda su magia se basa en que, al mirar el centro, sabe hacia qué lado seguir. Si los datos están desordenados, “menor” y “mayor” no significan nada y el método se viene abajo.

Esto crea un dilema práctico: ordenar también cuesta (lo veremos en las próximas entregas, y lo mejor es O(n log n)). Así que si solo vas a buscar una vez en datos desordenados, no compensa ordenar primero: tira de lineal. Pero si vas a buscar muchas veces en la misma colección, ordenar una vez y luego hacer mil búsquedas binarias es una ganancia enorme.

La diferencia, en números

Aquí está lo que justifica toda esta entrega. ¿Cuántos pasos da cada una en el peor caso?

  • Lineal, O(n): para un millón de elementos, hasta un millón de pasos.
  • Binaria, O(log n): para un millón de elementos, unos veinte pasos.

Veinte. Y no es porque el ejemplo esté elegido con trampa: como cada paso parte los datos por la mitad, el número de pasos es el número de veces que puedes dividir n entre dos hasta llegar a uno. Para mil millones de elementos, la binaria necesita unos treinta pasos. Treinta, para mil millones. Eso es lo que significa O(log n), y por eso es uno de los crecimientos más deseados que hay.

Iterativa o recursiva

El pseudocódigo de arriba es iterativo: usa un bucle MIENTRAS. Pero la búsqueda binaria también se puede escribir de forma recursiva, donde la función se llama a sí misma con la mitad que queda:

FUNCION binaria_rec(lista, objetivo, inicio, fin)
  SI inicio > fin ENTONCES RETORNAR -1
  medio = (inicio + fin) / 2
  SI lista[medio] == objetivo ENTONCES RETORNAR medio
  SI lista[medio] < objetivo ENTONCES
    RETORNAR binaria_rec(lista, objetivo, medio + 1, fin)
  SI NO
    RETORNAR binaria_rec(lista, objetivo, inicio, medio - 1)
  FIN SI
FIN FUNCION

Las dos hacen exactamente lo mismo y tienen la misma complejidad. La iterativa gasta menos memoria (no acumula llamadas); la recursiva se lee más cerca de la idea de “parte por la mitad y repite”. La recursión la veremos a fondo más adelante, así que si ahora te chirría un poco, tranquilo.

Casos de uso reales

La búsqueda binaria no es un ejercicio de pizarra, está por todas partes:

  • Cuando tu base de datos busca por un campo indexado, por dentro está haciendo algo muy parecido a una binaria (sobre estructuras de árbol).
  • Autocompletado, diccionarios, buscar una fecha en un registro ordenado de eventos.
  • En videojuegos y gráficos, para localizar rápido en tablas ordenadas.

Y la lineal, aunque “lenta”, es la correcta cuando los datos son pocos, están desordenados o solo vas a buscar una vez. No siempre gana el algoritmo más sofisticado: gana el que encaja con tu situación.

Una variante muy útil: el límite inferior

Hay una versión de la búsqueda binaria que no busca un valor exacto, sino la primera posición donde ese valor podría ir (lo que en muchos lenguajes se llama lower_bound). Sirve para insertar manteniendo el orden, para contar cuántos elementos son menores que uno dado o para buscar por rangos. Misma idea, mismo O(log n), pero resuelve un montón de problemas reales donde el “está o no está” se queda corto. Si dominas la binaria normal, esta variante es un superpoder casi gratis que conviene tener en el bolsillo.

El libro para esta entrega

La búsqueda binaria es, literalmente, el primer capítulo de Comprender los algoritmos, de Aditya Bhargava, y la explica con unos dibujos que se te quedan grabados. Si estás siguiendo la serie, es el compañero perfecto para esta entrega y las que vienen.

Lo siguiente: ordenar

Hemos visto que la búsqueda binaria es maravillosa, pero exige una cosa: que los datos estén ordenados. Y eso abre la siguiente gran pregunta de la serie: ¿cómo se ordena una colección?

En la próxima entrega empezamos por los tres métodos de ordenación sencillos: bubble, selection e insertion sort. Son lentos (todos O(n²)), pero son los que se entienden a la primera y los que te enseñan, de verdad, qué significa ordenar.

Preguntas frecuentes

¿Cuándo conviene la búsqueda lineal y cuándo la binaria?

Usa la binaria cuando la colección está ordenada y vas a buscar varias veces: es muchísimo más rápida, O(log n) frente a O(n). Usa la lineal cuando los datos están desordenados, son pocos, o solo vas a buscar una vez (porque ordenar primero costaría más de lo que ahorras). La binaria es más rápida, pero la lineal funciona siempre, sin requisitos.

¿Por qué la búsqueda binaria necesita el array ordenado?

Porque en cada paso mira el elemento central y decide hacia qué mitad seguir según si su objetivo es mayor o menor. Esa decisión solo tiene sentido si los datos están ordenados: así sabe que todo lo que hay a un lado es mayor y al otro menor. Sobre datos desordenados, “mayor” y “menor” no indican dónde seguir buscando, y el método falla.

¿Cuántos pasos da la búsqueda binaria?

Da del orden de log₂(n) pasos, es decir, las veces que puedes dividir n entre dos hasta llegar a uno. Para un millón de elementos son unos veinte pasos; para mil millones, unos treinta. Ese crecimiento tan lento es lo que la notación Big-O llama O(log n), y es lo que la hace tan rápida frente a la búsqueda lineal.

Este artículo contiene enlaces de afiliado.

Compártelo si te ha resultado útil.

¿Sabías que buscas en el diccionario con una búsqueda binaria sin haberlo estudiado nunca? Cuéntame.

Y… en la próxima entrega, a ordenar.

Artículos relacionados

Gráfica con varias curvas de crecimiento que se separan, de plana a exponencial, dibujada sobre una pizarra, ilustrando la notación Big-O

Qué es un algoritmo y la notación Big-O explicada paso a paso

Arranca la serie de Algoritmos, y lo hace por donde hay que empezar: aprendiendo a medir. Antes de comparar dos formas de resolver un problema necesitas saber cuál es mejor, y para eso está la notación Big-O. En esta primera entrega te explico qué es un algoritmo de verdad, qué es la complejidad temporal y espacial, y cómo leer esa notación que da tanto respeto: O(1), O(log n), O(n), O(n log n), O(n²) y la temida O(2^n). Lo verás con ejemplos cotidianos, sin matemáticas asustaviejas, y entenderás de una vez por qué un algoritmo puede tardar una décima de segundo y otro, con los mismos datos, dejarte el ordenador colgado una hora. Esto es la regla con la que se mide todo lo que viene después.

16:00 8 min Marcos Ramírez Lucía
Pizarra con un grafo de nodos y aristas dibujado a mano junto a flechas de un diagrama de ordenación, sobre una mesa con un portátil

Algoritmos desde cero: del bubble sort a A*, toda la serie

Si la serie de Fundamentos te enseñó a escribir programas que funcionan, esta te va a enseñar a escribir programas que funcionan bien: rápidos, eficientes y capaces de aguantar montañas de datos sin ahogarse. Arranco la serie de Algoritmos, dieciséis entregas, los lunes, miércoles y viernes, para recorrer los algoritmos y estructuras de datos más famosos y útiles que existen, los que resuelven los problemas de verdad: buscar, ordenar, recorrer grafos, optimizar y trabajar con texto. Empezamos por la notación Big-O (medir si un programa escala o se ahoga) y terminamos en A*, el algoritmo que usan los videojuegos para encontrar caminos. Es lenguaje-agnóstico, con pseudocódigo y ejemplos. Este post es el índice y el calendario completo.

16:00 8 min Marcos Ramírez Lucía
Lupa sobre líneas de código en una pantalla con una línea resaltada en rojo, como metáfora de buscar un error en un programa

Errores y depuración: aprende a arreglar tu propio código

Te lo digo después de treinta años: programar no es escribir código que funciona a la primera, es arreglar el que no funciona. El error no es el fracaso, es el día a día. En esta octava y última entrega de la serie de Fundamentos te enseño a convivir con los bugs: los tres tipos de error que existen (de sintaxis, de ejecución y de lógica), cómo leer un stack trace sin entrar en pánico, el try/catch para capturar fallos, la importancia de validar las entradas, y las dos grandes técnicas para cazar bugs: el print-debugging de toda la vida y el debugger con breakpoints. Cerramos con el puente a la serie de Algoritmos, donde la cosa se pone seria con la notación Big-O.

16:00 9 min Marcos Ramírez Lucía