La cerca dicotòmica (o binary search) és un algorisme eficient per localitzar un element dins d’un conjunt ordenat. El seu funcionament consisteix a dividir repetidament l’espai de cerca en dues meitats:
- Es comprova l’element central.
- Si és el valor buscat → finalitza la cerca.
- Si el valor és més petit → es continua per la meitat esquerra.
- Si és més gran → es continua per la meitat dreta.
Aquest procés té una complexitat O(log n), molt més eficient que la cerca seqüencial O(n).
En el context de Bases de Dades Relacionals
A les bases de dades relacionals, la cerca dicotòmica està estretament vinculada amb el funcionament dels índexs.
- Quan una taula disposa d’un índex (p. ex. sobre la clau primària), el motor de la base de dades pot trobar un registre concret sense haver de llegir totes les files.
- Els índexs es construeixen sovint amb estructures d’arbre B (B-Trees o B+Trees), que apliquen el principi de la divisió en meitats, igual que la cerca dicotòmica.
- Exemple: una consulta SELECT * FROM Clients WHERE id_client = 1050 en una taula amb milions de registres accedeix directament al punt adequat gràcies a aquest mecanisme.
Exemple senzill
Una taula ordenada per id:
[ 2, 5, 9, 14, 20, 33, 41, 57 ]
Cercar 20:
- Es mira el valor central 14.
- Com que 20 > 14, es busca a la meitat dreta.
- Nou subarray: [20, 33, 41, 57].
- Es comprova 33.
- Com que 20 < 33, es busca a la meitat esquerra.
- Es troba 20. ✔
