← Data structures from scratch · Lesson 16/32
Divide and conquer
Binary search: guess the number
If someone thinks of a number from 1 to 100 and tells you "higher" or "lower", you don't ask 1, 2, 3…: you say 50, and one answer throws away half. That's binary search, and it only works if the data is sorted.
You keep two indices, izq and der, marking where it can still be. You look at the middle one: if it's the one, done; if it's smaller than the target, everything to its left is out; if it's bigger, everything to its right. Each turn cuts the piece in half: O(log n).
$ node leccion.js
Press RUN (or Ctrl+Enter).
What to look at
- 23 shows up on the third look: 16 (too small, everything to its left is out), 56 (too big) and 23, at position 5. Ten numbers, three looks.
- 6 isn't there: it looks at 16, 5 and 8, then
izqpassesderand it returns −1.
The whole lesson on one page
Binary search: guess the number
If someone thinks of a number from 1 to 100 and tells you "higher" or "lower", you don't ask 1, 2, 3…: you say 50, and one answer throws away half. That's binary search, and it only works if the data is sorted.
You keep two indices, izq and der, marking where it can still be. You look at the middle one: if it's the one, done; if it's smaller than the target, everything to its left is out; if it's bigger, everything to its right. Each turn cuts the piece in half: O(log n).
function buscar(arr, objetivo) {
let izq = 0, der = arr.length - 1;
while (izq <= der) {
const medio = Math.floor((izq + der) / 2);
console.log("look", izq, "to", der, "-> middle", medio, "=", arr[medio]);
if (arr[medio] === objetivo) return medio;
if (arr[medio] < objetivo) izq = medio + 1; // it's to the right
else der = medio - 1; // it's to the left
}
return -1;
}
const numeros = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
console.log("position:", buscar(numeros, 23));
console.log("position:", buscar(numeros, 6));
- 23 shows up on the third look: 16 (too small, everything to its left is out), 56 (too big) and 23, at position 5. Ten numbers, three looks.
- 6 isn't there: it looks at 16, 5 and 8, then
izqpassesderand it returns −1.
The same idea, recursive
Binary search is the cleanest example of divide and conquer: the problem "is it in arr[izq..der]?" turns into the same problem on one half. Written recursively, the base case is the empty piece (izq > der) and each call gets one of the two halves.
Both versions do the same thing. The loop doesn't use stack; the recursive one looks more like how it's explained.
function buscarRec(arr, objetivo, izq = 0, der = arr.length - 1) {
if (izq > der) return -1; // empty piece: not there
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));
A million even numbers, and each search goes at most about 20 levels deep. 1,337,000 is at position 668,500; the odd one isn't there and returns −1.
Merge sort: split, sort, merge
Splitting works for sorting too: an array of one is already sorted (base case). A bigger one is split into two halves, each half is sorted by the same function, and at the end the two sorted halves are merged.
Merging is easy because both come in order already: compare the first of each and take the smaller one, like combining two face-up piles of cards.
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)); // whatever is left of either
}
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) + "merge", izq, "+", der, "->", r);
return r;
}
ordenar([38, 27, 43, 3, 9, 82, 10]);
Read top to bottom: first tiny pieces of one and two items are merged (the most indented, the deepest) and finally, with no indentation, merging the two big halves gives the whole array sorted.
Why O(n log n)
Count by levels. Halving over and over gives about log₂ n levels. On each level, across all the merges, every item is touched once: n steps per level. Total: n × log n.
A simple sort that compares every item with the others is O(n²). With a million items, that's the difference between about 20 million steps and a trillion. That's why languages ship sorts from this family: JavaScript's arr.sort() is 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, "| steps:", pasos, "| n·log2(n):", Math.round(n * Math.log2(n)), "| n²:", n * n);
}
The counted steps land right next to n·log2(n) and far from n²: with 100,000 items, under two million versus ten billion.