Búsqueda: lineal y binaria

Para encontrar un nombre en una lista ordenada de un millón, la búsqueda binaria nunca necesita más de 20 comprobaciones.

Buscar un valor

Buscar es el problema de encontrar dónde está un valor en una colección, o saber que no está. Tu celular lo hace cuando escribes el nombre de un contacto, una tienda lo hace cuando revisa si un artículo está en existencia, y un corrector ortográfico lo hace con cada palabra que escribes. La entrada es una lista y un valor objetivo. La salida es la posición del objetivo, o una señal como -1 que significa "no encontrado".

Búsqueda lineal: de uno en uno

El método más simple es empezar por la izquierda y revisar cada valor por turno hasta encontrar el objetivo o quedarse sin lista. Esto es la búsqueda lineal. Funciona con cualquier lista, ordenada o no. Su costo depende de la suerte: si el objetivo es el primero, basta con una comprobación; si es el último o no está, revisas todos los valores. Para una lista de n valores, el peor caso son n comprobaciones. Una lista del doble de larga puede llevar el doble de comprobaciones, y de ahí viene el nombre de "lineal": el trabajo crece en línea recta con el tamaño.

function linearSearch(list, target) {
  for (let i = 0; i < list.length; i++) {
    if (list[i] === target) return i;  // lo encontramos
  }
  return -1;                             // se revisó todo
}

Búsqueda binaria: partir por la mitad lo que queda

Si la lista está ordenada, se puede hacer mucho mejor. Piensa en el juego de adivinar un número: alguien elige un número del 1 al 100 y solo responde "más alto" o "más bajo". Un jugador sensato dice primero 50. Sea cual sea la respuesta, la mitad de las posibilidades desaparecen. El siguiente intento es el medio de lo que queda, y así sucesivamente. La búsqueda binaria hace exactamente esto con una lista ordenada. Guarda dos marcadores, lo y hi, alrededor de la parte donde todavía podría estar el objetivo. Revisa el valor del medio. Si es el objetivo, termina. Si el valor del medio es menor que el objetivo, todo lo que está a su izquierda también es menor, así que lo pasa más allá del medio. Si es mayor, hi pasa a antes del medio. Cuando lo rebasa a hi, ya no queda nada y el objetivo no está en la lista.

function binarySearch(list, target) {
  let lo = 0, hi = list.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (list[mid] === target) return mid;
    if (list[mid] < target) lo = mid + 1;  // el objetivo está a la derecha
    else hi = mid - 1;                     // el objetivo está a la izquierda
  }
  return -1;
}

¿Cuántas comprobaciones?

Cada comprobación de la búsqueda binaria reduce al menos a la mitad la parte que queda. Empezando con n valores, después de una comprobación quedan como mucho unos n/2, después de dos unos n/4, y así hasta que queda un solo valor. El número de mitades necesarias para pasar de n a 1 es el logaritmo en base 2 de n, que se escribe log₂ n. Contando también la última comprobación, la búsqueda binaria necesita como máximo ⌊log₂ n⌋ + 1 comprobaciones, donde ⌊ ⌋ significa redondear hacia abajo. Para 100 valores son 7 comprobaciones, y por eso el juego de adivinar siempre se puede ganar en 7 intentos. Para 1000 valores son 10, para un millón 20 y para mil millones 30.

La trampa: la lista debe estar ordenada

La búsqueda binaria solo funciona porque, en una lista ordenada, una comparación te dice de qué lado tiene que estar el objetivo. En una lista sin ordenar, el valor del medio no dice nada sobre sus vecinos, así que vuelves a la búsqueda lineal. Ordenar lleva su propio trabajo (de eso tratan las dos unidades siguientes), así que la elección depende del uso. Si buscas en una lista una sola vez, la búsqueda lineal puede ser lo más barato. Si buscas en la misma lista miles de veces, ordenarla una vez y luego usar la búsqueda binaria compensa enseguida. Este equilibrio entre preparar los datos y responder preguntas sobre ellos recorre toda la materia.