Binär sökning - ett av de enklaste sätten att hitta ett element i en array

Ganska ofta, programmerare, även nybörjare, inför det faktum att det finns en uppsättning siffror, som måste hitta ett visst nummer. Det är denna samling kallas en matris. Och för att hitta objekt i det, det finns en myriad olika sätt. Men den enklaste av dem kan betraktas som en binär sökning till höger. Vad är denna metod är? Och hur man ska genomföra binär sökning? Pascal är det enklaste miljö för att organisera ett sådant program, så vi kommer att använda den för att studera.

Först analysera, vad är fördelarna med denna metod är det så att vi kan förstå, vad är poängen i studien i ämnet. Så, låt oss ha en matris med en dimension av minst 100000000 element, som behöver att hitta några. Naturligtvis kan detta problem enkelt lösas genom en enkel linjär sökning där vi använder cykeln kommer att jämföra den nödvändiga element med alla dem som är i arrayen. Problemet är att genomförandet av denna idé kommer att ta för mycket tid. I en enkel Pascal program i flera behandlingar och tre rader huvudtexten, kommer du inte märker det, men när vi kommer till en mer eller mindre stora projekt med ett stort antal grenar och god funktion, kommer programmet att vara redo att laddas för länge. Speciellt om datorn är en svag utveckling. Därför finns det en binär sökning, vilket minskar söktiden minst två gånger.

Så, vad är principen bearbetning av denna metod? Omedelbart det borde säga att binär sökning fungerar inte i någon array, men bara på en sorterad uppsättning siffror. Vid varje steg som tas mitt element i arrayen (vilket innebär att antalet av elementet). Om den önskade numret är större än genomsnittet, då allt som är kvar är mindre än den genomsnittliga cell kan kasseras och inte titta där. Omvänt, om mindre än genomsnittet - bland dessa siffror till höger, kan du inte söka. Välj sedan en ny sökning, där det första elementet blir mitt element i hela gruppen och den sista och sista vilja. Det genomsnittliga antalet nya fältet kommer att vara en fjärdedel av hela segmentet, det vill säga, (det sista elementet + mittelementet av hela array) / 2. Igen, är samma operation utföras - en jämförelse med det genomsnittliga antalet av arrayen. Om målvärdet är mindre än genomsnittet, vi avvisar den högra sidan, och även för att göra härnäst, hittills denna mellersta del inte skulle önskas.

Naturligtvis är det bäst att titta på ett exempel på hur man skriver binär sökning. Pascal här kommer att passa alla - version är inte viktigt. Låt oss skriva ett enkelt program.

Det är en matris med en till h under namnet "massiv", en variabel som indikerar den undre gränsen för sökning, som kallas "Niz", den övre gränsen, som kallas "verh", den genomsnittliga sökord - "sredn"; och erforderligt antal - "isk".

Så först vi tilldelar den övre och nedre gränsen av intervallet Sök:

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

Sedan organisera cykeln "tills botten är mindre än den övre gränsen"

Medan Niz börja

Vid varje steg, delar vi segmentet 2:

sredn: = (Niz + verh) div 2; {Använd funktionen div eftersom klyftan utan resten}

Varje gång för omdömet. Eftersom objektet redan har konstaterats om mediet är önskvärd, avbryter cykeln:

іf sredn = isk sedan bryta;

Om mitten element i arrayen mer än önskas, kassera den vänstra sidan, det vill säga, den övre gränsen för den genomsnittliga utse elementet:

om massiv [sredn]> isk sedan verh: = sredn;

Och om tvärtom gör det undre gräns:

annars Niz: = sredn;
avsluta;

Det är allt som kommer att vara i programmet.

Låt oss fundera över hur det kommer att se den binära metoden i praktiken. Överväga denna array: 1, 3, 5, 7, 10, 12, 18 och det kommer att söka antalet 12.

Totalt har vi 7 element, så kommer den fjärde mediet, värdet 7.

Eftersom mer än 12, 7, 1.3 och 5 element, kan vi kasta. Sen har vi nummer 4, är 4/2 inga rester 2. Så kommer ett nytt element vara i genomsnitt 10.

Sedan 12 är större än 10, kasta vi 7. förblir endast 10, 12 och 18.

Här är den mellersta elementet redan 12, är det erforderligt antal. Denna uppgift är klar - nummer 12 tyckte.