Kërkimi Binary - një nga mënyrat më të lehta për të gjetur një element në një grup

Shumë shpesh, programuesit, edhe fillestar, të përballur me faktin se ka një grup të numrave, të cilat duhet të gjejnë një numër të caktuar. Është ky koleksion është quajtur një grup. Dhe për të gjetur artikuj në të, ka një numër të mënyra. Por shumica e thjeshtë prej tyre mund të konsiderohet një kërkim binar në të djathtë. Çfarë është kjo metodë është? Dhe si për të zbatuar kërkimin binar? Pascal është mjedisi më e lehtë për organizimin e një programi të tillë, kështu që ne do të përdorin atë për të studiuar.

Së pari, analizuar, cilat janë avantazhet e kësaj metode, ajo është kështu që ne mund të kuptojmë, çfarë është pika në studimin e temës. Pra, le të kemi një grup me një dimension të paktën 100000000 elemente, të cilat kanë nevojë për të gjetur disa. Natyrisht, ky problem mund të zgjidhet lehtë nga një kërkim të thjeshtë linear, në të cilën ne jemi duke përdorur ciklin do të krahasohen elementin e nevojshme me të gjithë ata që janë në rrjet. Problemi është se zbatimi i kësaj ideje do të marrë shumë kohë. Në një program të thjeshtë Pascal në disa trajtime, dhe tre rreshta të tekstit kryesor, ju nuk do të vini re atë, por kur kemi ardhur në një projekte më shumë ose më pak të mëdha, me një numër të madh të degëve dhe funksionalitetin të mirë, programi do të jetë gati për t'u ngarkuar për një kohë të gjatë. Sidomos në qoftë se kompjuteri është një performancë e dobët. Prandaj, ekziston një kërkim binar, e cila redukton kohën e kërkimit të paktën dy herë.

Pra, ajo që është parimi i punës i kësaj metode? Menjëherë duhet të them se kërkimi binar punon nuk është në asnjë grup, por vetëm në një grup të renditura të numrave. Në çdo element mesme hap marrë të array (që do të thotë numrin e elementit). Nëse kërkohet numri është më i madh se mesatarja, atëherë të gjitha që ka mbetur, që është më pak se qeliza mesatare, mund të hidhet dhe jo për të parë atje. Në anën tjetër, në qoftë se më pak se mesatarja - në mesin e këtyre numrave në të djathtë, ju nuk mund të kërkoni. Pastaj zgjidhni një fushë të re e kërkimit, ku elementi i parë do të jetë elementi mes të të gjithë grup, dhe e fundit dhe do të zgjasë. Numri mesatar i fushës së re do të jetë ¼ e të gjithë segmentit të, që është, (element i fundit + elementin e mesme të gjithë array) / 2. Përsëri, i njëjti operacion është kryer - një krahasim me numrin mesatar të vektorit. Nëse vlera synuar është më pak se mesatarja, ne e refuzojmë anën e djathtë, dhe gjithashtu të bëjë tjetër, deri më tani ky element e mesme nuk do të dëshiruar.

Sigurisht, është mirë që të shikojmë në një shembull se si të shkruajnë kërkimin binar. Pascal këtu do të përshtaten të gjithë - version nuk është e rëndësishme. Le të shkruaj një program të thjeshtë.

Kjo është një grup i 1 deri në h nën emrin "Massiv", një variabël tregon kufirin më të ulët të kontrollit, i quajtur "niz", kufiri i sipërm, i quajtur "verh", mesatarja afat kërkimi - "sredn"; dhe numri i kërkuar - "ISK".

Pra, së pari ne të caktojë kufirin e sipërme dhe të poshtme të kërkimit varg:

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

Pastaj të organizojnë ciklin "deri në fund është më pak se kufiri i sipërm":

Ndërsa niz filloj

Në çdo hap, ne ndarjen segmentin 2:

sredn: = (niz + verh) div 2; {Përdorni div funksion, për shkak të ndarjes pa mbetur}

Çdo herë e rishikimit. Për shkak se artikull është tashmë gjetur nëse medium është e dëshiruar, ndërpresë ciklin:

nëse sredn = ISK pastaj të thyer;

Nëse elementi mes të vektorit më shumë se e dëshiruar, hidhni nga e majta, që është, kufiri i sipërm i mesatares emërojë element:

nëse MASSIV [sredn]> ISK pastaj verh: = sredn;

Dhe në qoftë se në të kundërtën, kjo e bën kufirin më të ulët:

tjetër niz: = sredn;
fund;

Kjo është e gjitha që do të jetë në program.

Le të shqyrtojmë se si do të duket metodën binar në praktikë. Konsideroni këtë grup: 1, 3, 5, 7, 10, 12, 18 dhe se do të kërkojë numrin 12.

Në total ne kemi 7 elemente, kështu do të mesme katërt, vlera 7.

Që prej më shumë se 12, 7, 1.3 dhe 5 elemente, ne mund të hidhni. Pastaj ne kemi marrë numrin 4, 4/2 asnjë mbetje është 2. Pra, një element i ri do të jetë një mesatare prej 10.

Që nga 12 është më i madh se 10, ne hidhni 7. mbetet vetëm 10, 12 dhe 18.

Këtu, elementi mesme është tashmë 12, është numri i kërkuar. Kjo detyrë është përfunduar - numri 12 gjetur.