Binary zoeken - een van de makkelijkste manieren om een element in een array te vinden

Heel vaak, programmeurs, zelfs beginners, geconfronteerd met het feit dat er een set van nummers, die een bepaald nummer moet vinden. Het is deze collectie wordt een array genoemd. En om items in te vinden, zijn er een groot aantal manieren. Maar de meest eenvoudige van hen kan worden beschouwd als een binary search aan de rechterkant. Wat is deze methode is? En hoe binary search uit te voeren? Pascal is de makkelijkste omgeving voor de organisatie van een dergelijk programma, dus we zullen het gebruiken om te studeren.

Ten eerste, te analyseren, wat zijn de voordelen van deze methode, het is dus we kunnen begrijpen, wat is het punt in de studie van het onderwerp. Dus, laten we een array met een afmeting van ten minste 100000000 elementen, die moeten vinden sommigen. Vanzelfsprekend kan dit probleem eenvoudig worden opgelost door een eenvoudige lineair zoeken, waarbij we met de cyclus het gewenste element te vergelijken met die in de array. Het probleem is dat de uitvoering van dit idee te veel tijd in beslag neemt. In een eenvoudige Pascal programma in verschillende behandelingen, en drie lijnen van de hoofdtekst, zul je niet merken, maar als we naar een meer of minder grote projecten met een groot aantal van de takken en een goede functionaliteit te komen, zal het programma klaar om te worden geladen voor te lang. Vooral als de computer is een zwakke prestatie. Daarom is er een binary search, die zoektijd minstens twee keer vermindert.

Dus, wat is het werkingsprincipe van deze methode? Onmiddellijk moet zeggen dat binary search werkt is op geen enkele array, maar alleen op een gesorteerde reeks getallen. Bij elke stap genomen middenelement van de matrix (dat wil zeggen de van het element). Als het vereiste getal groter is dan het gemiddelde, dan is alles wat overblijft, die kleiner is dan de gemiddelde cel, kunnen worden weggegooid en niet om daar te kijken. Omgekeerd, als minder dan het gemiddelde - een van die nummers aan de rechterkant, kun je niet zoeken. Selecteer vervolgens een nieuw zoekgebied, waar het eerste element het middelste element van de hele array, en de laatste en de laatste zal zijn. Het gemiddelde aantal nieuw veld zal ¼ van het segment, dat wil zeggen (+ het laatste element het middenelement van de gehele array) / 2. Opnieuw wordt dezelfde bewerking uitgevoerd - een vergelijking met het gemiddelde aantal van de array. Als de streefwaarde minder dan het gemiddelde is, verwerpen wij de juiste kant, en ook nu te doen, tot nu toe dit middelste element zou niet gewenst.

Natuurlijk, is het het beste om te kijken naar een voorbeeld van hoe binary search schrijven. Pascal hier zal iedereen past - versie is niet belangrijk. Laten we schrijven een eenvoudig programma.

Het is een array met 1 uur onder de naam "massief", een variabele waarin de ondergrens van het onderzoek, genoemd "niz", de bovengrens, genaamd "verh", de gemiddelde zoekterm - "sredn"; en het vereiste aantal - "isk".

Dus, eerst wijzen we de boven- en ondergrens van het bereik zoeken:

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

organiseert dan de cyclus "tot onderaan kleiner is dan de bovengrens":

Terwijl niz beginnen

Bij elke stap delen we het segment 2:

sredn: = (niz + verh) div 2; {Gebruik de functie div, omdat de kloof zonder rest}

Elk moment van beoordeling. Omdat het object reeds is vastgesteld wanneer het medium wordt gewenst, onderbrekingscyclus:

іf sredn = isk dan breken;

Als het middelste element van de array meer dan gewenst, gooi de linkerzijde, dat is, de bovengrens van de gemiddelde benoemen element:

Als MASSIV [sredn]> isk dan verh: = sredn;

En als integendeel, het maakt de ondergrens:

anders niz: = sredn;
end;

Dat is alles wat die zullen worden in het programma.

Laten we eens kijken hoe het de binaire methode eruit zal zien in de praktijk. Beschouw deze array: 1, 3, 5, 7, 10, 12, 18 en zal het getal 12 te zoeken.

In totaal hebben we 7 elementen, zo zal de vierde mediumdoorvoeren, de waarde 7.

Sinds meer dan 12, 7, 1,3 en 5 elementen, kunnen we weggooien. Dan hebben we het nummer 4 kregen, 4/2 geen residu is 2. Dus zal een nieuw element een gemiddelde van 10 zijn.

Sinds 12 groter is dan 10, gooi wij 7. blijft slechts 10, 12 en 18.

Hier, de middelste element is al 12, is het vereiste aantal. Deze taak is voltooid - nummer 12 gevonden.