A ricerca binaria hè unu di i modi più faciuli di truvà un elementu in un array

A spessu, i programaturi, ancu i principianti, anu face cun u fattu chì ci hè un nùmeru di numeri in quale hè necessariu di truvà un certu numaru. Sta cullizzioni hè chjamata un array. È per truvà l'elementu ghjustu in questu, ci sò assai modi. Ma a più sèmplice entre elle hè a ricerca binaria. Chì hè u metudu? E cumu implementà una ricerca binaria? Pascal hè l'ambienti megliu per l'urganizazione di u prugramma, perchè a usà di studià.

Prima, avemu analizà quelli chì l'avvanzi di stu modu sò, dopu à tuttu, per pudemu capisce, Chì hè u puntu di studià stu tema. Allora, suppone chì ci hè un array cù una dimensione di almenu 10 000 000 000 elementi, in quale avete bisognu di truvà unu specicu. Di sicuru, stu prublema ponu esse risoltu cun una ricerca lineale simplice, in quale usamu un loop per paragunate l'elementu cun qualchissia cù tutti quelli chì esistinu in u duminiu. U prublema hè chì l'implementazione di sta idea pigghianu assai tempu. Nta un prugramma simplici Pascal per parechji prucessi è cù trè linea di u testu principalu, ùn avè micca avvistatu, ma quandu hà principiatu prughjetti più o menu maiò cù assai ramificazione è boni funziunalità, u prugramma finitu serà carricu assai. In particulare se l'ordinateur hà u poviru rolu. Cusì, ci hè una ricerca binaria, chì reduci u tempu di ricerca per almenu duie volte.

Allora, chì hè u principiu di stu modu? Immediatamente vale degnu di dì chì i ricerca binaria ùn viaghja n qualchi varietà, ma solu in un settore selezziunatu di numeri. À ogni passu prossimu, l'elementu pruduzzione di l'array hè presu (cunfirmendu à u numeru d'elementi). Sì u numaru persequitatu hè più grande ca u mediu, allura tuttu ciò chì hè nantu à a manca, questu, hè menu di l'elementu mediu, pò esse rimiati è micca cercati. Inoltre, quandu si menzu di u mediu, trà e nummari à u dirittu, ùn pudere micca circà. Appena aghjustatu un novu area di ricerca, induve l'elementu intermediu di u gruppu sanu seranu u primu elementu, è l'ultimu seranu l'ultimu. U numaru mediu di a nova zona serà ¼ de u segmentu sanu, questu hè (l'ultimu elementu + l'elementu mediu di tutta a matriu) / 2. Doppu, a stessa operazione hè stata - paragunii cù u numaru mediu di u dispusitivu. Se u valore sceltu hè menu di a medità, descarca u manu diritta, è fate a listessa finu à chì questu l'elementu mediu hè stati trovi.

Sicura chì u megliu modu di vede l'esempiu hè cumu scrive una cerca binariu. Pascal hè adattatu à alcuni - a versione ùn hè micca impurtante. Scrivemu un prugrammu simplici.

Havi avè un array from 1 to h named "massiv", una variable chì denota una circunsultazione di ricerca inferior, chjamata "niz", un upper bound imsejja "verh", l'elementu di circuszione media hè "sredn"; U numaru dumandatu hè "isk".

Allora, prima assignà i limiti supiriori è inferjuri di l'intervalu di ricerca:

Niz: = 1;
Verh: = h + 1;

Allora si organizzemu u ciculu "mentri u fondu hè menu di u limitu massimu":

Mentri era Cumincià

À ogni passu, dividite u segmentu da 2:

Sredn: = (niz + verh) div 2; {Aduprate a funzione div divulgazione di u restu}

Ogni vota facemu un verificatu. Se a media hè uguaglianza à u desideriu, interruce u ciculu, postu chì l'elementu cumpostu hè digià trottu:

Іf sredn = s'ellu hè prestu;

Se l'elementu intermediu di u dispunìbu hè più grande di quellu chì cercanu, discendemu u partitu hè statu, questu l'elementu mediu à a fruntiera:

Sè massiv [sredn]> sec esse verh: = sredn;

E se à u cuntrariu, pudemu fà u limitu più limitatu:

Ùn ci hè: = sredn;
End;

Hè tuttu ciò chì serà in u prugramma.

Avemu l'analisi di u modu di u metudu binariu in a prutica. Piglia una talia: 1, 3, 5, 7, 10, 12, 18 è cercate u numeru 12 in questu.

In u settore, avemu 7 elementu, perchè u migliu serà u quartu, u so valore 7.

Cum'ellu 12 hè più grande di 7, l'elementi 1,3 è 5 pò esse scartate. Dopu, avemu 4 numeri partuti, 4/2 senza restu hè 2. Allora, u novu elementu intermediu sarà 10.

Dopu 12 hè più di 10, discardemu 7. Solu 10, 12 è 18 sò partuti.

Eccu l'elementu media hè digià 12, questu hè u numeru dumandatu. A cumpagnia hè cumplerta - u numuru 12 hè truvatu.