Ir al contenido
Ayotl
English

← Estructuras de datos desde cero · Lección 16/32

Divide y vencerás

✕
1/10

Búsqueda binaria: adivina el número

Si alguien piensa un número del 1 al 100 y te dice «más alto» o «más bajo», no preguntas 1, 2, 3…: dices 50, y con una respuesta descartas la mitad. Eso es la búsqueda binaria, y sólo funciona si los datos están ordenados.

Se guardan dos índices, izq y der, que marcan dónde todavía puede estar. Se mira el de en medio: si es, listo; si es menor que lo buscado, todo lo de su izquierda sobra; si es mayor, todo lo de su derecha. Cada vuelta parte el pedazo a la mitad: O(log n).

258121623385672910123456789izq ↓medio ↓der ↓
leccion.js

$ node leccion.js

Pulsa CORRER (o Ctrl+Enter).

Qué mirar

  • El 23 aparece a la tercera mirada: el 16 (chico, todo lo de su izquierda sobra), el 56 (grande) y el 23, en la posición 5. Diez números, tres miradas.
  • El 6 no está: mira el 16, el 5 y el 8, y entonces izq rebasa a der y sale −1.
Toda la lección en una página

Búsqueda binaria: adivina el número

Si alguien piensa un número del 1 al 100 y te dice «más alto» o «más bajo», no preguntas 1, 2, 3…: dices 50, y con una respuesta descartas la mitad. Eso es la búsqueda binaria, y sólo funciona si los datos están ordenados.

Se guardan dos índices, izq y der, que marcan dónde todavía puede estar. Se mira el de en medio: si es, listo; si es menor que lo buscado, todo lo de su izquierda sobra; si es mayor, todo lo de su derecha. Cada vuelta parte el pedazo a la mitad: O(log n).

258121623385672910123456789izq ↓medio ↓der ↓
function buscar(arr, objetivo) {
  let izq = 0, der = arr.length - 1;
  while (izq <= der) {
    const medio = Math.floor((izq + der) / 2);
    console.log("miro", izq, "a", der, "-> medio", medio, "=", arr[medio]);
    if (arr[medio] === objetivo) return medio;
    if (arr[medio] < objetivo) izq = medio + 1;   // está a la derecha
    else der = medio - 1;                         // está a la izquierda
  }
  return -1;
}

const numeros = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
console.log("posición:", buscar(numeros, 23));
console.log("posición:", buscar(numeros, 6));
  • El 23 aparece a la tercera mirada: el 16 (chico, todo lo de su izquierda sobra), el 56 (grande) y el 23, en la posición 5. Diez números, tres miradas.
  • El 6 no está: mira el 16, el 5 y el 8, y entonces izq rebasa a der y sale −1.

La misma idea, recursiva

La búsqueda binaria es el ejemplo más limpio de divide y vencerás: el problema «¿está en arr[izq..der]?» se convierte en el mismo problema sobre una mitad. Escrita recursiva, el caso base es el pedazo vacío (izq > der) y cada llamada recibe una de las dos mitades.

Las dos versiones hacen lo mismo. La del ciclo no gasta pila; la recursiva se parece más a cómo se explica.

function buscarRec(arr, objetivo, izq = 0, der = arr.length - 1) {
  if (izq > der) return -1;                     // pedazo vacío: no está
  const medio = Math.floor((izq + der) / 2);
  if (arr[medio] === objetivo) return medio;
  if (arr[medio] < objetivo) return buscarRec(arr, objetivo, medio + 1, der);
  return buscarRec(arr, objetivo, izq, medio - 1);
}

const pares = [];
for (let i = 0; i < 1000000; i++) pares.push(i * 2);

console.log(buscarRec(pares, 1337000));
console.log(buscarRec(pares, 1337001));

Un millón de números pares, y cada búsqueda baja a lo más unos 20 niveles de recursión. 1 337 000 está en la posición 668 500; el impar no está y sale −1.

Merge sort: partir, ordenar, mezclar

Para ordenar también sirve partir: un arreglo de uno ya está ordenado (caso base). Uno más grande se parte en dos mitades, cada mitad se ordena con la misma función, y al final se mezclan las dos mitades ordenadas.

Mezclar es fácil porque las dos ya vienen en orden: se comparan los primeros de cada una y se toma el más chico, como juntar dos montones de cartas boca arriba.

function mezclar(a, b) {
  const r = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) r.push(a[i++]);
    else r.push(b[j++]);
  }
  return r.concat(a.slice(i), b.slice(j));   // lo que sobre de alguna
}

function ordenar(arr, nivel = 0) {
  if (arr.length <= 1) return arr;
  const medio = Math.floor(arr.length / 2);
  const izq = ordenar(arr.slice(0, medio), nivel + 1);
  const der = ordenar(arr.slice(medio), nivel + 1);
  const r = mezclar(izq, der);
  console.log("  ".repeat(nivel) + "mezclo", izq, "+", der, "->", r);
  return r;
}

ordenar([38, 27, 43, 3, 9, 82, 10]);

Lee de arriba abajo: primero se mezclan pedacitos de uno y dos elementos (los más sangrados, los más profundos) y al final, sin sangría, la mezcla de las dos mitades grandes da el arreglo entero ordenado.

Por qué O(n log n)

Cuenta por niveles. Partir a la mitad una y otra vez da unos log₂ n niveles. En cada nivel, entre todas las mezclas se toca cada elemento una vez: n pasos por nivel. Total: n × log n.

Un ordenamiento sencillo que compara cada elemento con los demás es O(n²). Con un millón de datos, la diferencia es entre unos 20 millones de pasos y un billón. Por eso los lenguajes traen ordenamientos de esta familia: arr.sort() de JavaScript es O(n log n).

let pasos = 0;
function mezclar(a, b) {
  const r = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) { pasos++; r.push(a[i] <= b[j] ? a[i++] : b[j++]); }
  pasos += (a.length - i) + (b.length - j);
  return r.concat(a.slice(i), b.slice(j));
}
function ordenar(arr) {
  if (arr.length <= 1) return arr;
  const m = Math.floor(arr.length / 2);
  return mezclar(ordenar(arr.slice(0, m)), ordenar(arr.slice(m)));
}

for (const n of [8, 1024, 100000]) {
  const datos = Array.from({ length: n }, (_, i) => (i * 7919) % n);
  pasos = 0;
  ordenar(datos);
  console.log("n =", n, "| pasos:", pasos, "| n·log2(n):", Math.round(n * Math.log2(n)), "| n²:", n * n);
}

Los pasos contados salen pegados a n·log2(n) y muy lejos de n²: con 100 000 datos, menos de dos millones contra diez mil millones.

Practica con un reto en vídeo

Para leer más