Cautarea Binara.docx

CĂUTARE BINARĂ Căutarea binară este un mod ușor de căutare al unor elemente într-un vector sortat într-un timp mai mic. Aceasta are un algoritm destul de simplu de ințeles. Avem două contoare st(stânga) și dr(dreapta).Prima oară vom inițializa st=1 și dr=n.După vom verifica dacă mijlocul dintre ele este egal un elementul cautat.Dacă nu este avem două cazuri. 1.element căutat > v[mij] => elementul se află în dreapta lui mijl deci stânga devine mijl+1. 2.element căutat< v[mijl] =>elementul se aflăînstângaluimijldecidreaptadevine mijl-1. Algoritmularatăastfel while(st<=dr){ mijl=(st+dr)/2; if(v[mijl]==elem) ///daca am gasitelementul. { poz=mijl; ///retinpozitia st=dr+1; ///opresc while-ul. } else if(v[mijl]<elem) /// daca e in dreapta st=mijl+1; /// mutstmai in dreapta else ///daca e in stanga dr=mijl-1; ///mut dr mai in stanga Acesta are o complexitateO(log n). Pentru o sortare rapidă puteți folosi funcția sort din biblioteca algorithm. sort(v+1,v+n+1);