Binær søgning - en af de nemmeste måder at finde et element i et array

Ganske ofte, programmører, selv begyndere, konfronteret med det faktum, at der er et sæt tal, der skal finde et bestemt nummer. Det er denne samling kaldes et array. Og for at finde elementer i det, er der et utal af måder. Men den mest enkle af dem kan betragtes som en binær søgning til højre. Hvad er denne metode er? Og hvordan man gennemfører binær søgning? Pascal er den nemmeste miljø for organiseringen af et sådant program, så vi vil bruge det til at studere.

Først analysere, hvad er fordelene ved denne metode, er det så vi kan forstå, hvad er pointen i studiet af emnet. Så lad os få et array med en dimension på mindst 100.000.000 elementer, som har brug for at finde nogle. Selvfølgelig kan dette problem let løses ved en simpel lineær søgning, hvor vi bruger cyklen vil sammenligne den ønskede element med alle dem, der er i opstillingen. Problemet er, at gennemførelsen af denne idé vil tage for meget tid. I en enkel Pascal program i flere behandlinger, og tre linjer af hovedteksten, vil du ikke mærke det, men når vi kommer til en mere eller mindre store projekter med et stort antal filialer og god funktionalitet, vil programmet være klar til at blive lastet for længe. Især hvis computeren er en svag præstation. Derfor er der en binær søgning, hvilket reducerer søgetiden mindst to gange.

Så hvad er arbejdsmiljøet Princippet i denne metode? Umiddelbart bør det sige, at binær søgning virker, er ikke på nogen array, men kun på en sorteret sæt tal. Ved hvert skridt taget midterste element i array (hvilket betyder, at antallet af elementet). Hvis det krævede antal er større end gennemsnittet, så alt, hvad der er tilbage, som er mindre end den gennemsnitlige celle, kan kasseres, og ikke at se der. Omvendt, hvis mindre end gennemsnittet - blandt disse numre til højre, kan du ikke søge. Vælg derefter en ny søgning område, hvor det første element vil være den midterste del af hele systemet, og den sidste og den sidste vilje. Det gennemsnitlige antal nye område vil være ¼ af alt det segment, der er, (det sidste element + det midterste element i hele systemet) / 2. Igen er den samme operation udføres - en sammenligning med det gennemsnitlige antal af array'et. Hvis målet er mindre end gennemsnittet, vi afviser højre side, og også at gøre næste, indtil nu denne midterste element ville ikke ønskes.

Selvfølgelig er det bedst at se på et eksempel på, hvordan man skriver binær søgning. Pascal her passer nogen - version er ikke vigtigt. Lad os skrive et simpelt program.

Det er en vifte af 1 til h under navnet "massiv", en variabel der angiver den nedre grænse for søgningen, kaldet "niz", den øvre grænse, kaldet "Verh", den gennemsnitlige søgeord - "sredn"; og det nødvendige antal - "isk".

Så først vi tildeler den øvre og nedre grænse af intervallet søgning:

niz: = 1;
Verh: = h + 1;

Så organisere cyklus "indtil bunden er mindre end den øvre grænse":

Mens niz begynde

På hvert trin, opdeler vi segment 2:

sredn: = (niz + Verh) div 2; {Brug funktionen div, fordi den kløft uden resten}

Hver gang af revision. Fordi elementet allerede er blevet fundet, hvis der ønskes mediet, afbryde cyklus:

hvis sredn = isk derefter bryde;

Hvis den midterste element i arrayet mere end ønsket, kasseres den venstre side, det vil sige den øvre grænse af gennemsnittet udpege element:

hvis Massiv [sredn]> isk derefter Verh: = sredn;

Og hvis tværtimod, det gør den nedre grænse:

ellers niz: = sredn;
ende;

Det er alt, der vil være i programmet.

Lad os overveje, hvordan det vil se den binære metode i praksis. Overveje dette array: 1, 3, 5, 7, 10, 12, 18 og den vil søge tallet 12.

I alt har vi 7 elementer, så vil den fjerde medium, værdien 7.

Da mere end 12, 7, 1,3 og 5 elementer, kan vi kassere. Så har vi fået nummer 4, 4/2 ingen rester er 2. Så vil et nyt element være et gennemsnit på 10.

Siden 12 er større end 10, vi kassere 7. forbliver kun 10, 12 og 18.

Her, den midterste element er allerede 12, er det nødvendige antal. Denne opgave er afsluttet - nummer 12 fundet.