Binêre soek - een van die maklikste maniere om 'n element in 'n skikking te vind

Dikwels, programmeerders, selfs beginners, gekonfronteer met die feit dat daar 'n stel getalle, wat 'n spesifieke aantal moet vind. Dit is hierdie versameling is 'n skikking met die naam. En om items in dit vind, is daar 'n magdom van maniere. Maar die mees eenvoudige van hulle kan beskou word as 'n binêre soek aan die regterkant. Wat is hierdie metode is? En hoe om binêre soek implementeer? Pascal is die maklikste omgewing vir die organisasie van so 'n program, so ons sal dit gebruik om te studeer.

In die eerste plek te ontleed, wat is die voordele van hierdie metode, dit is, sodat ons kan verstaan, Wat is die punt in die studie van die onderwerp. So, laat ons 'n skikking met 'n dimensie van ten minste 100000000 elemente, wat nodig het om 'n paar te vind. Natuurlik, kan hierdie probleem maklik opgelos word deur 'n eenvoudige lineêre soek, waarin ons met behulp van die siklus sal die vereiste element vergelyk met almal wat in die skikking. Die probleem is dat die implementering van hierdie idee te veel tyd in beslag neem. In 'n eenvoudige Pascal program in verskeie behandelings, en drie lyne van die hoofteks, sal jy nie agterkom nie, maar wanneer ons na 'n min of meer groot projekte met 'n groot aantal takke en 'n goeie funksie kom, sal die program gereed om gelaai te lank wees. Veral as die rekenaar is 'n swak prestasie. Daar is dus 'n binêre soek, wat soek tyd ten minste twee keer verminder.

So, wat is die werksbeginsel van hierdie metode? Onmiddellik dit moet sê dat binêre soek werk is nie in enige skikking, maar net op 'n gesorteerde stel nommers. By elke stap geneem middel element van die skikking (wat beteken dat die aantal van die element). As die vereiste getal is groter as die gemiddelde, dan sal al wat oorbly, wat minder is as die gemiddelde sel, kan weggegooi word en nie om daar te kyk. Aan die ander kant, indien minder as die gemiddelde - onder diegene getalle tot die reg, jy kan nie soek. Kies dan 'n nuwe soek area, waar die eerste element in die middel element van die hele reeks, en die laaste en die laaste testament sal wees. Die gemiddelde aantal nuwe veld sal wees ¼ van al die segment, dit is, (die laaste element + die middel element van die hele reeks) / 2. Weereens, is dieselfde operasie uitgevoer - 'n vergelyking met die gemiddelde getal van die skikking. As die teiken waarde minder as die gemiddelde is, verwerp ons die regte kant, en ook om volgende te doen, tot nou toe hierdie middel element sou nie skaam word.

Natuurlik, dit is die beste om te kyk na 'n voorbeeld van hoe om binêre soek skryf. Pascal hier sal iemand pas - weergawe is nie belangrik nie. Ons skryf 'n eenvoudige program.

Dit is 'n verskeidenheid van 1 tot h onder die naam "massief", 'n veranderlike wat die onderste grens van die search, die sogenaamde "niz", die boonste perk, met die naam "verh", die gemiddelde navraag - "sredn"; en die vereiste aantal - "ISK".

So, die eerste wat ons ken die boonste en onderste grens van die reeks search:

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

organiseer dan die siklus "totdat die onderkant is minder as die boonste perk":

Terwyl niz begin

By elke stap, verdeel ons die segment 2:

sredn: = (niz + verh) div 2; {Gebruik die funksie div, want die kloof sonder res}

Elke keer van hersiening. Omdat die item is reeds gevind as die medium verlang, onderbreek siklus:

іf sredn = ISK dan breek;

As die middel element van die skikking meer as jy wil, gooi die linkerkant, dit wil sê die boonste grens van die gemiddelde aanstel element:

As massief [sredn]> ISK dan verh: = sredn;

En as inteendeel, dit maak die onderste grens:

anders niz: = sredn;
eindig;

Dit is alles wat sal wees in die program.

Kom ons kyk na hoe dit die binêre metode sal kyk in die praktyk. Oorweeg hierdie reeks: 1, 3, 5, 7, 10, 12, 18 en dit sal die nommer 12 soek.

In totaal het ons 7 elemente, so sal die vierde medium, die waarde 7.

Sedert meer as 12, 7, 1.3 en 5 elemente, kan ons weggooi. Toe het ons die nommer 4 het, 02/04 geen oorskot 2. So, sal 'n nuwe element 'n gemiddeld van 10 wees.

Sedert 12 is groter as 10, weggooi ons 7. bly net 10, 12 en 18.

Hier is die middelste element is reeds 12, dit is die vereiste aantal. Hierdie taak voltooi is - nommer 12 gevind.