cautarea binara
DESCRIPTION
Cautarea binaraTRANSCRIPT
Algoritmul de cutare binar ofer performane mai bune dect algoritmul de cutare secvenial. El funcioneaz astfel: se compar numrul de cutat cu elementul aflat la mijlocul irului (element care se mai numete i pivot). n cazul n care cele dou elemente coincid cutarea s-a ncheiat cu succes. Dac numrul de cutat este mai mare dect pivotul, se continu cutarea n aceeai manier n subirul delimitat de pivot i captul irului iniial. Dac numrul de cutat este mai mic dect pivotul se continu cutarea n aceeai manier n subirul delimitat de pivot i nceputul irului iniial. Algoritmul prezentat se ncadreaz n clasa algoritmilor elaborai conform tehnicii de programare Divide et Impera. Unul din dezavantajele acestui algoritm este c irul n care se face cutarea trebuie s fie iniial sortat.PSEUDOCOD:Este dat un vectorK cuNelemente n ordine cresctoare ,acest algoritm face o cutare pentru un element avnd valoareaX. VariabileleLOW,MIDDLE siHIGHnoteaz limita inferoar , mijlocul si limita superioar a intervalului de cutare . Functia returneaz indexul elemntului dac avemcutare cu succes,altfel returneaz0.Pasul1. LOW:= 1HIGH := NPasul2.Repet pasii 3, 4 pn cnd LOW K [ MIDDLE ]atunciLOW := MIDDLE + 1altfelcutare cu succes returneaz MIDDLEPasul5.Cutare fr succes returneaz0Pasul 1 initializeaz variabileleLOWsiHIGH, pasul 3 calculeaz valoarea variabileiMIDDLE, care este mijlocul tabelei .Pasul 4 face comparatiile ntre cheia de cutat si valorile limit si returneaz cheia cutata dac este gsit .Pasul 5 returneaz valoarea0 insemnnd cutare fr succes .