Voordat we Binair zoeken leren, leren we:
Wat is zoeken?
Zoeken is een hulpprogramma waarmee de gebruiker documenten, bestanden, media of elk ander type gegevens in een database kan vinden. Zoeken werkt volgens het simpele principe van het matchen van de criteria met de records en het tonen aan de gebruiker. Op deze manier werkt de meest elementaire zoekfunctie.
Wat is binair zoeken?
Een binaire zoekopdracht is een geavanceerd zoekalgoritme dat gegevens uit een gesorteerde lijst met items zoekt en ophaalt. Het belangrijkste werkingsprincipe is dat de gegevens in de lijst in tweeën worden gedeeld totdat de vereiste waarde is gevonden en aan de gebruiker wordt weergegeven in het zoekresultaat. Binair zoeken is algemeen bekend als een zoekopdracht met een halve interval of een logaritmische zoekopdracht .
In deze zelfstudie over algoritmen leert u:
- Wat is zoeken?
- Wat is binair zoeken?
- Hoe werkt binair zoeken?
- Voorbeeld binaire zoekopdracht
- Waarom hebben we binair zoeken nodig?
Hoe werkt binair zoeken?
De binaire zoekopdracht werkt op de volgende manier:
- Het zoekproces wordt gestart door het middelste element van de gesorteerde reeks gegevens te lokaliseren
- Daarna wordt de sleutelwaarde vergeleken met het element
- Als de sleutelwaarde kleiner is dan het middelste element, analyseert de zoekactie de bovenste waarden naar het middelste element voor vergelijking en afstemming
- In het geval dat de sleutelwaarde groter is dan het middelste element, analyseert de zoekactie de lagere waarden naar het middelste element voor vergelijking en afstemming
Voorbeeld binaire zoekopdracht
Laten we eens kijken naar het voorbeeld van een woordenboek. Als u een bepaald woord moet vinden, doorloopt niemand elk woord op een opeenvolgende manier, maar zoekt willekeurig de dichtstbijzijnde woorden om naar het vereiste woord te zoeken.
De bovenstaande afbeelding illustreert het volgende:
- Je hebt een array van 10 cijfers en 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 wij nemen de bodemwaarde. Daarom is het midden 4.
- Het algoritme laat alle elementen van de middelste (4) naar de laagste grens vallen omdat 59 groter is dan 24, en nu blijft de array met slechts 5 elementen over.
- Nu is 59 groter dan 45 en kleiner dan 63. Het midden is 7. Daarom wordt de rechterindexwaarde midden - 1, wat gelijk is aan 6, en blijft de linkerindexwaarde hetzelfde als voorheen, namelijk 5.
- Op dit punt weet je dat 59 na 45 komt. Daarom wordt de linker index, 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 de binaire zoekopdracht te begrijpen
- U hebt een reeks gesorteerde waarden variërend van 2 tot 20 en u moet 18 lokaliseren.
- Het gemiddelde van de onder- en bovengrenzen is (l + r) / 2 = 4. De gezochte waarde is groter dan het midden, namelijk 4.
- De matrixwaarden kleiner dan het midden worden uit de zoekactie verwijderd en waarden groter dan de middenwaarde 4 worden doorzocht.
- Dit is een terugkerend opsplitsingsproces totdat het daadwerkelijke item dat moet worden doorzocht, is gevonden.
Waarom hebben we binair zoeken nodig?
De volgende redenen maken de binaire zoekopdracht een betere keuze om als zoekalgoritme te gebruiken:
- 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, krijgt het binaire algoritme willekeurig toegang tot 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 met gelijkheidsvergelijkingen, die langzamer en meestal onnauwkeurig zijn.
- Na elke zoekcyclus deelt 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
Overzicht
- Zoeken is een hulpprogramma waarmee de gebruiker naar documenten, bestanden en andere soorten gegevens kan zoeken. Een binaire zoekopdracht is een geavanceerd zoekalgoritme dat gegevens uit een gesorteerde lijst met items zoekt en ophaalt.
- Binair zoeken is algemeen bekend als een zoekopdracht met een halve interval of een logaritmische zoekopdracht
- Het werkt door de array in tweeën te delen bij elke iteratie onder het vereiste element dat wordt gevonden.
- Het binaire algoritme neemt het midden van de array in door de som van de meest linkse en meest rechtse indexwaarden te delen door 2. Nu laat het algoritme de onder- of bovengrens van elementen uit het midden van de array vallen, afhankelijk van het element dat moet worden gevonden .
- Het algoritme benadert 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 met gelijkheidsvergelijkingen die traag en onnauwkeurig zijn.
- Een binaire zoekopdracht is niet geschikt voor ongesorteerde gegevens.