Binary søk - en av de enkleste måtene å finne et element i en matrise

Ganske ofte, programmerere, selv nybegynnere, møtt med det faktum at det er et sett med tall, som må finne en bestemt nummer. Det er denne samlingen kalles en matrise. Og for å finne elementer i det, er det et mylder av måter. Men den enkleste av dem kan betraktes som en binær søk til høyre. Hva er denne metoden er? Og hvordan å implementere binære søk? Pascal er den enkleste miljø for organisering av et slikt program, så vi bruker den til å studere.

Først, analysere, hva er fordelene med denne metoden, er det slik at vi kan forstå, hva er poenget i studiet av emnet. Så, la oss ta en matrise med en dimensjon på minst 100.000.000 elementer som trenger å finne noen. Selvfølgelig kan dette problemet enkelt løses ved en enkel lineær søk, der vi bruker syklusen vil sammenligne den nødvendige element med alle de som er i matrisen. Problemet er at gjennomføringen av denne ideen vil ta for mye tid. I en enkel Pascal program i flere behandlinger, og tre linjer med hovedteksten, vil du ikke merke det, men når vi kommer til en mer eller mindre store prosjekter med et stort antall greiner og god funksjonalitet, vil programmet være klar til å bli lastet for lenge. Spesielt hvis maskinen er en svak ytelse. Derfor er det en binær søk, noe som reduserer søketiden minst to ganger.

Så, hva er arbeids Prinsippet for denne metoden? Umiddelbart bør det si at binære søk fungerer ikke på noen array, men bare på en sortert sett med tall. Ved hvert skritt tatt midt element i gruppen (dvs. antall av elementet). Dersom det nødvendige antallet er større enn gjennomsnittet, så alt som er igjen, som er mindre enn gjennomsnittet celle, kan kastes og ikke å se det. Derimot, hvis mindre enn gjennomsnittet - blant disse tallene til høyre, du kan ikke søke. Deretter velger du en ny søkeområde, hvor det første elementet vil være midt element av hele gruppen, og den siste og den siste vilje. Det gjennomsnittlige antall nye feltet vil være fjerdedel av hele segmentet, det vil si, (det siste elementet + midten element av hele gruppen) / 2. Igjen blir den samme operasjon utført - en sammenligning med det midlere antall av tabellen. Hvis målet verdien er mindre enn gjennomsnittet, avviser vi på høyre side, og også for å gjøre videre, til nå denne middel element ville ikke ønskelig.

Selvfølgelig er det best å se på et eksempel på hvordan du skal skrive binære søk. Pascal her vil passe alle - versjonen er ikke viktig. La oss skrive et enkelt program.

Det er en rekke 1 til h under navnet "massiv", en variabel som angir den nedre grense av søket, kalt "Niz", den øvre grense, kalt "verh", den gjennomsnittlige søketermen - "sredn"; og det nødvendige antall - "isk".

Så først tildeler vi den øvre og nedre grense for området ditt:

Niz: = 1;
verh: = h + 1;

Deretter organisere syklusen "før bunnen er mindre enn den øvre grensen":

Mens Niz begynne

På hvert trinn, deler vi segment 2:

sredn: = (Niz + verh) div 2; {Bruk funksjonen div, fordi skillet uten rest}

Hver gang for anmeldelse. På grunn av at elementet har allerede blitt funnet dersom mediet er ønsket, avbryte syklusen:

hvis sredn = isk deretter bryte;

Hvis den midtre element i matrisen mer enn ønskelig, kast på venstre side, det vil si, den øvre grense for den gjennomsnittlige utnevne element:

hvis massiv [sredn]> isk deretter verh: = sredn;

Og hvis tvert imot, det gjør den nedre grense:

annet Niz: = sredn;
end;

Det er alt som skal være i programmet.

La oss vurdere hvordan det vil se den binære metoden i praksis. Tenk på dette matrise: 1, 3, 5, 7, 10, 12, 18 og det vil søke nummer 12.

Totalt har vi 7 elementer, så vil den fjerde medium, verdien 7.

Siden mer enn 12, 7, 1,3 og 5 elementer, kan vi forkaste. Da har vi fått nummer fire, er 4/2 ingen rester 2. Så vil et nytt element være et gjennomsnitt på 10.

Siden 12 er større enn 10, forkaste vi 7. bare gjenstår 10, 12 og 18.

Her er den midterste element allerede 12, er det nødvendige antall. Denne oppgaven er ferdig - nummer 12 funnet.