Kërkimi binar
Në shkencat kompjuterike, kërkimi binar (anglisht:binary search) është një algoritëm kërkimi që gjen pozicionin e elementit të kërkuar në një vektor të renditur.[1][2] Kërkimi binar krahason vlerën që kërkohet me elmentin e mesit të vektorit; nëse këto vlera nuk janë të barabarta, gjysma tek e cila elementi i kërkuar nuk mund te gjendet eleminohet dhe kërkimi fillon në gjysmën tjetër dhe vazhdon në këtë mënyrë derisa të gjendet pozicioni i elementit të kërkuar. Nëse kërkimi përfundon duke qenë bosh gjysma e mbetur, atëherë elementi i kërkuar nuk është në vektor.
Kërkimi binar në rastin më të keq ka kompleksitet logaritmik në kohë duke bërë O(log n) krahasime, ku n është numri i elementeve të vektorit. Kërkimi binar ka kompleksitet konstant (O(1)) në hapësire, që do të thotë që hapësira që kërkohet nga algoritmi nuk varet nga numri i elementeve të vektorit.[3] Megjithëse në disa struktura të dhënash të projektuara për kërkim të shpejtë—siç janë tabelat hash—kërkimi është më eficient, kërkimi binar aplikohet në një gamë më të gjerë problemesh.
Megjithëse ideja është e thjeshtë, implementimi i kërkimit binar në menyrën e duhur kërkon vëmendje ndaj disa hollësive rreth kushteve të përfundimit të algoritmit dhe llogaritjes së pozicionit të mesit.
Ekzistojnë shumë variante të kërkimit binar. Për shembull, kërkimi eksponencial e zgjeron kërkimin binar edhe në listat e pakufizuara. Strukturat e të dhënave si pema binare e kërkimit dhe pema B bazohen mbi kërkimin binar.
Algoritmi
RedaktoKërkimi binar funksionon vetëm në vektorët e renditur. Kërkimi binar fillon duke krahasuar elementin e mesit të vektorit me elementin që kërkohet. Nëse vlera e kërkuar është sa elementi i mesit, atëherë kthehet pozicioni i tij në vektor. Nëse vlera që kërkohet është me e vogël ose më e madhe se elementi i mesit, kërkimi vazhdon në gjysmën e poshtme ose gjysmën e sipërme të vektorit, përkatësisht, duke mos e konsideruar më gjysmën tjetër.[4]
Procedura
RedaktoNëse jepet një vektor A me n elemente me vlera A0, A1, ..., An−1, të renditura në mënyrë të tillë që A0 ≤ A1 ≤ ... ≤ An−1, dhe jepet gjithashtu vlera që kërkohet T, funksioni i mëposhtëm përdor kërkimin binar për të gjetur indeksin e T në vektorin A.[4]
- Barazo L me 0 dhe R me n − 1.
- Nëse L > R, kërkimi mbyllet në mënyrë jo të suksesshme.
- Barazo m (pozicioni i elementit të mesit) me (L + R) / 2.
- Nëse Am < T, barazo L me m + 1 dhe shko te hapi 2.
- Nëse Am > T, barazo R me m − 1 dhe shko te hapi 2.
- Tani Am = T, kërkimi përfundoi; kthe m.
Kjo procedurë iterative kontrollon kufinjtë e kërimit me dy variabla. Disa implementime mund të kontrollojnë nëse elementi i mesit është i barabartë me vlerën e kërkuar në fund të procedurës. Kjo çon në një cikël më të shpejtë krahasimi, por kërkon më shume krahasime në rastin mesatar.[5]
Referime
Redakto- ^ Cormen etj. 2009, f. 39.
- ^ Eric W. Weisstein, Kërkimi binar nga MathWorld.
- ^ Flores, Ivan; Madpis, George (1971). "Average binary search length for dense ordered lists". Communications of the ACM. 14 (9): 602–603. doi:10.1145/362663.362752.
{{cite journal}}: Mungon ose është bosh parametri|language=(Ndihmë!) - ^ a b Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm B".
- ^ Bottenbruch, Hermann (1962). "Structure and Use of ALGOL 60". Journal of the ACM. 9 (2): 161–211. doi:10.1145/321119.321120.
{{cite journal}}: Mungon ose është bosh parametri|language=(Ndihmë!) Procedure is described at p. 214 (§43), titled "Program for Binary Search".