Căutare binară - una dintre cele mai simple moduri de a găsi un element într-o matrice

Destul de des, programatori, chiar și începători, care se confruntă cu faptul că există un set de numere, care trebuie să găsească un anumit număr. Este această colecție se numește o matrice. Și pentru a găsi elemente în ea, există o multitudine de moduri. Dar cea mai simplă dintre ele poate fi considerată o căutare binară pe dreapta. Ce este această metodă este? Și cum să pună în aplicare binar de căutare? Pascal este cel mai simplu mediu pentru organizarea unui astfel de program, asa ca vom folosi pentru a studia.

În primul rând, analiza, care sunt avantajele acestei metode, este astfel încât să putem înțelege, ceea ce este punctul în studiul subiectului. Deci, să avem un tablou cu o dimensiune de cel puțin 100000000 elemente, care au nevoie pentru a găsi unele. 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ă punerea în aplicare a acestei idei va dura prea mult timp. Î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 computerul este o performanță slabă. Prin urmare, există o căutare binară, care reduce timpul de căutare cel puțin de două ori.

Deci, ceea ce este principiul de lucru al acestei metode? Imediat trebuie să spunem că funcționează binar de căutare nu este în nici un tablou, dar numai pe un set sortat de numere. La fiecare element de mijloc pas făcut de matrice (adică numărul elementului). În cazul în care este necesar numărul este mai mare decât media, atunci tot ce rămâne, care este mai mică decât celula medie, pot fi eliminate și nu să se uite acolo. În schimb, dacă este mai mică decât media - printre aceste numere la dreapta, nu poți căuta. Apoi selectați o nouă zonă de căutare, în cazul în care primul element va fi elementul de mijloc al întregii matrice și ultima și ultima voință. Numărul mediu de câmp nou va fi ¼ din toate segment, adică, (ultimul element + elementul de mijloc al întregii matrice) / 2. Din nou, aceeași operație se realizează - o comparație cu numărul mediu de matrice. Dacă valoarea țintă este mai mică decât media, respingem pe partea dreapta, și, de asemenea, să facă în continuare, până în prezent acest element de mijloc nu ar fi dorit.

Desigur, cel mai bine este să se uite la un exemplu de cum se scrie binar de căutare. Pascal aici se va potrivi cu oricine - versiune nu este important. Să scrie un program simplu.

Este o matrice de 1 h sub denumirea de „Massiv“, o variabilă care indică limita inferioară a căutării, numită „niz“, limita superioară, numită „VERH“, media de căutare termenul - „sredn“; și numărul necesar - „ISK“.

Deci, mai întâi vom atribui limita superioară și inferioară a căutării intervalului:

niz: = 1;
VERH: = h + 1;

Apoi, organizează ciclul „până în partea de jos este mai mică decât limita superioară“:

In timp ce NIZ începe

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

sredn: = (niz + VERH) div 2; {Utilizați div-funcție, deoarece decalajul fără rest}

De fiecare dată de revizuire. Deoarece elementul a fost deja găsit, dacă se dorește mediul, întrerupe ciclul:

іf sredn = isk apoi rupe;

În cazul în care elementul de mijloc al matrice mai mult de dorit, aruncați partea stângă, adică, limita superioară a mediei numește element de:

dacă massiv [sredn]> isk apoi VERH: = sredn;

Și dacă, dimpotrivă, face limita de jos:

altceva NIZ: = sredn;
se încheie;

Asta e tot ce va fi în program.

Să luăm în considerare modul în care va arăta metoda binară în practică. Luați în considerare această matrice: 1, 3, 5, 7, 10, 12, 18 și va căuta numărul 12.

În total avem 7 elemente, astfel încât va de-al patrulea mediu, valoarea 7.

Din moment ce mai mult de 12, 7, 1.3 și 5 elemente, putem debarasa. Apoi ne-am luat numărul 4, 4/2 nici un reziduu este 2. Deci, un element nou va fi o medie de 10.

Deoarece 12 este mai mare de 10, renunțăm la 7. rămâne doar 10, 12 și 18.

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