Ganske ofte programmerere, til og med nybegynnere,overfor det faktum at det er et sett med tall du trenger for å finne et visst antall. Denne samlingen kalles en matrise. Og for å finne ønsket element i det, er det et stort utvalg av måter. Men de enkleste blant dem kan med rette betraktes som et binært søk. Hva er den gitte metoden? Og hvordan implementere binært søk? Pascal er det enkleste miljøet for å organisere et slikt program, så vi vil bruke det til studier.
Først skal vi se på fordelene med denne metoden, fordi vi kan forstå
Så hva er prinsippet med dettemetode? Det er verdt å si med en gang at binærsøk ikke fungerer i noen matrise, men bare i et sortert sett med tall. På hvert neste trinn tas det midtre elementet i matrisen (som betyr antallet av elementet). Hvis ønsket antall er større enn gjennomsnittet, kan alt som er til venstre, det vil si mindre enn det midtre elementet, kastes og ikke søkes der. Omvendt, hvis mindre enn gjennomsnittet - blant tallene til høyre, kan du ikke søke. Deretter velger vi et nytt søkeområde, der det første elementet vil være det midtre elementet i hele matrisen, og det siste vil forbli det siste. Gjennomsnittlig antall for den nye regionen vil være ¼ av hele segmentet, det vil si (det siste elementet + det midtre elementet i hele matrisen) / 2. Igjen utføres den samme operasjonen - sammenligning med gjennomsnittlig antall av matrisen. Hvis ønsket verdi er mindre enn gjennomsnittet, kasserer vi høyre side og gjør det samme videre til dette midtre elementet er funnet.
Selvfølgelig er det best å se på et eksempel på hvordan binært søk skrives. Pascal passer for alle her - versjonen er ikke viktig. La oss skrive et enkelt program.
Den vil ha en matrise fra 1 til t"massiv", en variabel som angir den nedre grensen til søket med navnet "niz", den øvre grensen kalt "verh", det midtre elementet i søket er "sredn"; og nummeret du leter etter isk.
Så først tilordner vi øvre og nedre grenser for søkeintervallet:
nederst: = 1;
verh: = h + 1;
Deretter organiserer vi syklusen "mens den nedre er mindre enn den øvre grensen":
Mens niz
Del segmentet med 2 på hvert trinn:
sredn: = (niz + verh) div 2; {bruk div-funksjon fordi vi deler uten resten}
Hver gang vi sjekker. Hvis gjennomsnittet er lik det ønskede, avbryter vi syklusen, siden det ønskede elementet allerede er funnet:
hvis sredn = isk så bryte;
Hvis det midtre elementet i matrisen er større enn det ønskede, kaster vi venstre side, det vil si at vi tildeler det midtre elementet til den øvre grensen:
hvis matrise yusrednsch> søksmål øverst: = gjennomsnitt;
Og hvis tvert imot, så gjør vi det til den nedre grensen:
annet bunn: = gjennomsnitt;
end;
Det er alt som vil være i programmet.
La oss se hvordan den binære metoden vil se ut i praksis. La oss ta et slikt utvalg: 1, 3, 5, 7, 10, 12, 18 og vi vil se etter tallet 12 i det.
Totalt har vi 7 elementer, så det fjerde vil være gjennomsnittet, dets verdi er 7.
| 1 | 3 | 5 | 7 | 10 | 12 | 18 |
Siden 12 er større enn 7, kan vi forkaste elementene 1,3 og 5. Så har vi 4 tall igjen, 4/2 uten resten er 2. Så det nye midtelementet blir 10.
| 7 | 10 | 12 | 18 |
Her er det midtre elementet allerede 12, dette er ønsket antall. Oppgave fullført - nummer 12 funnet.
