Binair zoekalgoritme met VOORBEELD

Voordat we binair zoeken leren, laten we het volgende leren:

Wat is zoeken?

Zoeken is een hulpprogramma waarmee de gebruiker documenten, bestanden, media of andere soorten gegevens in een database kan vinden. Zoeken werkt volgens het eenvoudige principe om de criteria aan de records te koppelen en deze aan de gebruiker weer te geven. Op deze manier werkt de meest elementaire zoekfunctie.

Wat is binair zoeken?

Een binaire zoekopdracht is een geavanceerd type zoekalgoritme dat gegevens uit een gesorteerde lijst met items vindt en ophaalt. Het belangrijkste werkprincipe is het verdelen van de gegevens in de lijst in tweeën totdat de vereiste waarde is gevonden en aan de gebruiker wordt weergegeven in het zoekresultaat. Binaire zoekopdracht staat algemeen bekend als een half interval zoeken nodig heeft of logaritmisch zoeken.

Hoe binair zoeken werkt?

Het binaire zoeken werkt op de volgende manier:

Het zoekproces begint met het lokaliseren van het middelste element van de gesorteerde reeks gegevens
Daarna wordt de sleutelwaarde vergeleken met het element
Als de sleutelwaarde kleiner is dan het middelste element, analyseert zoekopdrachten de bovenste waarden naar het middelste element voor vergelijking en matching
Als de sleutelwaarde groter is dan het middelste element, analyseert de zoekopdracht de lagere waarden naar het middelste element voor vergelijking en matching

Voorbeeld binaire zoekopdracht

Laten we eens kijken naar het voorbeeld van een woordenboek. Als je een bepaald woord moet vinden, doorloopt niemand elk woord op een sequentiële manier, maar zoekt willekeurig naar de dichtstbijzijnde woorden om naar het gewenste woord te zoeken.

De bovenstaande afbeelding illustreert het volgende:

Je hebt een array van 10 cijfers en het element 59 moet worden gevonden.
Alle elementen zijn gemarkeerd met de index van 0 – 9. Nu wordt het midden van de array berekend. Om dit te doen, neemt u de meest linkse en meest rechtse waarden van de index en deelt u deze door 2. Het resultaat is 4.5, maar we nemen de minimumwaarde. Het midden is dus 4.
Het algoritme laat alle elementen van het midden (4) naar de laagste grens vallen omdat 59 groter is dan 24, en nu heeft de array nog maar 5 elementen.
Nu is 59 groter dan 45 en kleiner dan 63. De middelste is 7. Daarom wordt de rechter indexwaarde midden – 1, wat gelijk is aan 6, en de linker indexwaarde blijft hetzelfde als voorheen, namelijk 5.
Op dit punt weet je dat 59 na 45 komt. Daarom wordt de linkerindex, die 5 is, ook midden.
Deze iteraties gaan door totdat de array is teruggebracht tot slechts één element, of het te vinden item het midden van de array wordt.

Voorbeeld 2

Laten we naar het volgende voorbeeld kijken om de werking van het binaire zoeken te begrijpen

Je hebt een reeks gesorteerde waarden variërend van 2 tot 20 en je moet 18 vinden.
Het gemiddelde van de onder- en bovengrens is (l + r) / 2 = 4. De gezochte waarde is groter dan het midden, namelijk 4.
De arraywaarden kleiner dan het midden worden uit de zoekopdracht verwijderd en waarden groter dan de middenwaarde 4 worden doorzocht.
Dit is een zich herhalend verdeelproces totdat het eigenlijke te zoeken item is gevonden.

Waarom hebben we binair zoeken nodig?

De volgende redenen maken binair zoeken een betere keuze voor gebruik als zoekalgoritme:

Binair zoeken werkt efficiënt op gesorteerde gegevens, ongeacht de grootte van de gegevens
In plaats van de zoekopdracht uit te voeren door de gegevens in een reeks te doorlopen, gebruikt het binaire algoritme willekeurig de gegevens om het vereiste element te vinden. Dit maakt de zoekcycli korter en nauwkeuriger.
Binair zoeken voert vergelijkingen uit van de gesorteerde gegevens op basis van een ordeningsprincipe dan het gebruik van gelijkheidsvergelijkingen, die langzamer en meestal onnauwkeurig zijn.
Na elke zoekcyclus verdeelt het algoritme de grootte van de array in tweeën, dus in de volgende iteratie werkt het alleen in de resterende helft van de array

Leer onze volgende tutorial van Lineair zoeken: Python, C++ Voorbeeld

Samenvatting

Zoeken is een hulpprogramma waarmee de gebruiker naar documenten, bestanden en andere soorten gegevens kan zoeken. Een binaire zoekopdracht is een geavanceerd type zoekalgoritme dat gegevens uit een gesorteerde lijst met items vindt en ophaalt.
Binair zoeken is algemeen bekend als zoeken met een half interval of logaritmisch zoeken
Het werkt door de array in tweeën te delen bij elke iteratie onder het vereiste element dat wordt gevonden.
Ocuco's Medewerkers binair algoritme neemt het midden van de array door de som van de meest linkse en meest rechtse indexwaarden te delen door 2. Nu laat het algoritme de onder- of bovengrens van de elementen uit het midden van de array vallen, afhankelijk van het te vinden element.
Het algoritme gebruikt willekeurig de gegevens om het vereiste element te vinden. Dit maakt de zoekcycli korter en nauwkeuriger.
Bij binair zoeken worden de gesorteerde gegevens vergeleken op basis van een ordeningsprincipe, in plaats van op gelijkheidsvergelijkingen die langzaam en onnauwkeurig zijn.
Een binaire zoekopdracht is niet geschikt voor ongesorteerde gegevens.