Aceasta operatie se numeste indexare. Ce-i drept, constructia vectorului $Ind$ nu se poate face intr-un timp mai bun decat $O(N log N)$, dar dupa ce acest lucru se face (o singura data, la inceputul programului), cautarile se pot face foarte repede. Daca pe parcurs se fac adaugari sau stergeri de elemente in/din baza de date, se va pierde catva timp pentru mentinerea indexului, dar in practica timpul acesta este mult mai mic decat timpul care s-ar pierde cu cautarea unor elemente in cazul in care vectorul ar fi neindexat. Nu vom intra in detalii despre indexare, deoarece nu acesta este obiectul capitolului de fata.

In unele situatii nu se poate face nici indexarea structurii de date. Sa consideram cazul unui program care joaca sah. Numarul de pozitii posibile ale pieselor pe tabla de sah este mult prea mare. Nu poate fi vorba nici de retinerea tuturor, cu atat mai putin de indexarea lor. In esenta, modul de functionare al acestui program se reduce la o rutina care primeste o pozitie pe tabla si o variabila care indica daca la mutare este albul sau negrul, rutina intorcand cea mai buna mutare care se poate efectua din acea pozitie. Majoritatea programelor de sah incep sa expandeze respectiva pozitie, examinand tot felul de variante ce pot decurge din ea si alegand-o pe cea mai promitatoare, asa cum fac si jucatorii umani. Pozitiile analizate sunt stocate in memorie sub forma unei liste simplu inlantuite.

In unele situatii nu se poate face nici indexarea structurii de date. Sa consideram cazul unui program care joaca sah. Numarul de pozitii posibile ale pieselor pe tabla de sah este mult prea mare. Nu poate fi vorba nici de retinerea tuturor, cu atat mai putin de indexarea lor. In esenta, modul de functionare al acestui program se reduce la o rutina care primeste o pozitie pe tabla si o variabila care indica daca la mutare este albul sau negrul, rutina intorcand cea mai buna mutare care se poate efectua din acea pozitie. Majoritatea programelor de sah incep sa expandeze respectiva pozitie, examinand tot felul de variante ce pot decurge din ea si alegand-o pe cea mai promitatoare, asa cum fac si jucatorii umani. Pozitiile analizate, fiind mult mai putine decat cele posibile, sunt stocate in memorie sub forma unei liste.

Sa ne inchipuim acum urmatoarea situatie. Este posibil ca, prin expandarea unei configuratii initiale a tablei sa se ajunga la aceeasi configuratie finala pe doua cai diferite. Spre exemplu, daca albul muta intai calul la _f3_, apoi nebunul la _c4_, pozitia rezultata va fi aceeasi ca si cand s-ar fi mutat intai nebunul si apoi calul (considerand bineinteles ca negrul da in ambele situatii aceeasi replica). Daca configuratia finala a fost deja analizata pentru prima varianta, este inutil sa o mai analizam si pentru cea de-a doua, pentru ca rezultatul (concluzia la care se va ajunge) va fi exact acelasi. Dar cum isi poate da programul seama daca pozitia pe care are de gand s-o analizeze a fost analizata deja sau nu ?