... u 1pn si kp-1 a kp.Pentru rezolvarea acestei probleme vom descrie mai multi subalgoritmi.O prima metoda este cautarea secventiala, in care sunt examinate succesiv toate cheile.Subalgoritmul CautSecva,n,K,p esteInN, n1 siSIk1 k2 .... knSISe cauta p astfel caSIp1 si a k1 sau pn1 si aknSIsau 1pn si kp-1 a kp. Fie p0ICazul inca negasitS Daca ak1 atunci p1 altfel Daca akn atunci pn1 altfel Pentru i2 n executa Daca p0 si aki atunci pi sfdaca sfpentru sfdaca sfdacasf-CautSecvSe observa ca prin aceasta metoda se vor executa in cel mai nefavorabil caz n-1 comparari, intrucat contorul i va lua toate valorile de la 2 la n. Cele n chei impart axa reala in n1 intervale. Tot atatea comparari se vor efectua in n-1 din cele n1 intervale in care se poate afla cheia cautata, deci complexitatea medie are acelasi ordin de marime ca si complexitatea in cel mai rau caz.Evident ca in multe situatii acest algoritm face calcule inutile. Atunci cand a fost deja gasita cheia dorita este inutil a parcurge ciclul pentru celelalte valori ale lui i. Cu alte cuvinte este posibil sa inlocuim ciclul PENTRU cu un ciclu CTTIMP. Ajungem la un al doilea algoritm, dat in continuare.Subalgoritmul CautSucca,n,K,p esteInN, n1 siSIk1 k2 .... knSISe cauta p astfel caSIp1 si a k1 sau pn1 si aknSIsau 1pn si kp-1 a kp. Fie p1 Daca ak1 atunci Cattimp pn si akp executs pp1 sfcat sfdacasf-CautSecvO alta metoda, numita cautare binara, care este mult mai eficienta, utilizeaza tehnica divide et impera privitor la date. Se determina in ce relatie se afla cheia articolului aflat in mijlocul colectiei cu cheia de cautare. In urma acestei verificari cautarea se continua doar intr-o jumatate a colectiei. In acest mod, prin injumatatiri succesive se micsoreaza volumul colectiei ramase pentru cautare. Cau ... Download