Căutarea binară este una dintre cele mai simple căi de a găsi un element dintr-o matrice

Destul de des, programatorii, chiar și începătorii, se confruntă cu faptul că există un set de numere în care este necesar să se găsească un anumit număr. Această colecție este numită matrice. Și pentru a găsi elementul potrivit în ea, există o mulțime de moduri. Dar cea mai simplă dintre ele de drept poate fi considerată o căutare binară. Care este metoda? Și cum să implementați o căutare binară? Pascal este cel mai simplu mijloc pentru organizarea unui astfel de program, așa că îl vom folosi pentru studiu.

În primul rând, vom analiza care sunt avantajele acestei metode, la urma urmei, astfel încât să putem înțelege, care este punctul în studierea acestui subiect. Deci, să presupunem că există o matrice cu o dimensiune de cel puțin 100000000 elemente, în care trebuie să găsiți un anumit. Desigur, această problemă poate fi rezolvată ușor printr-o căutare liniară simplă, în care folosim ciclul va compara elementul necesar cu toți cei care sunt în matrice. Problema este că implementarea acestei idei va dura prea mult. Într-un program Pascal simplu în mai multe tratamente, și trei linii de text de bază, nu se va observa, dar când am ajuns la o serie de proiecte mai mult sau mai puțin mari, cu un număr mare de sucursale și o bună funcționalitate, programul va fi gata pentru a fi încărcate pentru prea mult timp. Mai ales în cazul în care calculatorul are o performanță slabă. Prin urmare, există o căutare binară, care reduce timpul de căutare cel puțin de două ori.

Deci, care este principiul acestei metode? Merită menționat faptul că căutarea binară nu funcționează în niciun fel de matrice, ci numai într-un set sortat de numere. La fiecare pas următor, se ia elementul de mijloc al matricei (referindu-se la numărul elementului). Dacă doriți mai mult înseamnă că tot ceea ce este la stânga, adică mai puțin decât elementul mediu, poate fi aruncat și nu poate fi cercetat acolo. În schimb, dacă este mai mică decât media, printre numerele din dreapta, nu le puteți căuta. Apoi, vom selecta o nouă zonă de căutare, în care elementul de mijloc al întregului matrice va fi primul element, iar ultimul va rămâne ultimul. Numărul mediu de noi zone va fi frac14 este lungimea totală, adică (ultimul element + elementul de mijloc al matricei întregi) / 2. Din nou, se efectuează aceeași operație - comparație cu numărul mediu al matricei. Dacă valoarea dorită este mai mică decât media, aruncați partea dreaptă și faceți același lucru până când se găsește acest element intermediar.

Desigur, este mai bine să analizăm un exemplu de scriere a unei căutări binare. Pascal aici este potrivit pentru oricine - versiunea nu este importantă. Să scriem un program simplu.

Este o matrice de 1 h sub denumirea de „Massiv“, o variabilă care indică o limită de căutare inferioară, numită „niz“, limita superioară, numită „VERH“, căutarea medie termenul - „sredn“ - și numărul necesar - „isk“.

Deci, mai întâi alocați limitele superioare și inferioare ale intervalului de căutare:

niz: = 1-
verh: = h + 1;

Apoi organizăm ciclul "în timp ce fundul este mai mic decât limita superioară":

În timp ce niz < verh - 1 nu
începe

La fiecare pas, împărțiți segmentul cu 2:

sredn: = (niz + verh) div 2- {utilizați funcția div, deoarece împărțim restul}

De fiecare dată când efectuăm un cec. Dacă media este egală cu cea dorită, întrerupem ciclul, deoarece elementul dorit este deja găsit:

dacă sredn = isk apoi pauză;

Dacă elementul mediu al matricei este mai mare decât cel pe care îl căutăm, aruncați partea stângă, adică atribuim elementul de mijloc limita superioară:

dacă masiv [sredn]> isk apoi verh: = sredn;

Și dacă dimpotrivă, atunci facem limita inferioară:

altfel niz: = sredn-
se încheie;

Asta-i tot ce va fi în program.

Vom analiza modul în care metoda binară va arăta în practică. Luăm o astfel de matrice: 1, 3, 5, 7, 10, 12, 18 și căutați numărul 12 în el.

În total, avem 7 elemente, deci media va fi a patra, valoarea ei 7.

Din moment ce 12 este mai mare de 7, elementele 1,3 și 5 pot fi aruncate. Apoi, avem 4 numere ramase, 4/2 fara restul fiind 2. Astfel, noul element de mijloc va fi 10.

Din moment ce 12 este mai mult de 10, aruncați 7. Numai 10, 12 și 18 sunt lăsate.

Aici elementul de mijloc este deja 12, acesta este numărul necesar. Sarcina este finalizată - numărul 12 este găsit.