Binair zoekalgoritme met VOORBEELD

Voordat we binair zoeken gaan leren, laten we eerst eens kijken wat zoeken precies is.

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 zoekalgoritme dat gegevens vindt en ophaalt uit een gesorteerde lijst. Het kernprincipe is het halveren van de gegevens in de lijst totdat de gewenste waarde is gevonden en aan de gebruiker wordt getoond in de zoekresultaten. Binaire zoekopdrachten worden ook wel aangeduid 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 in de gesorteerde gegevensreeks.
• Daarna wordt de sleutelwaarde vergeleken met het element.
• Als de sleutelwaarde kleiner is dan het middelste element, analyseert de zoekfunctie de waarden boven het middelste element ter vergelijking en matching.
• Als de sleutelwaarde groter is dan het middelste element, analyseert de zoekfunctie de lagere waarden ten opzichte van het middelste element voor vergelijking en matching.

Binair zoekalgoritme (pseudocode)

De binaire zoekmethode kan worden geschreven als een korte, iteratieve routine. Deze houdt twee pointers bij, een lage en een hoge, en verkleint het zoekbereik totdat het doel is gevonden of het bereik leeg is.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

De routine retourneert de index van het doel bij succes en -1 als de waarde niet aanwezig is. Omdat het bereik bij elke iteratie halveert, wordt de lus maximaal log₂(n) keer uitgevoerd.

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:

1. Je hebt een array van 10 cijfers en het element 59 moet worden gevonden.
2. Alle elementen zijn gemarkeerd met een index van 0 tot en met 9. Nu berekenen we het midden van de array. Hiervoor nemen we de meest linkse en meest rechtse indexwaarden en delen deze door 2. Het resultaat is 4.5, maar we ronden af ​​naar beneden. Vandaar dat het midden 4 is.
3. Het algoritme verwijdert alle elementen van het midden (4) tot aan de laagste grens, omdat 59 groter is dan 24, en de array bevat nu nog maar 5 elementen.
4. Nu is 59 groter dan 45 en kleiner dan 63. Het midden is 7. Daarom wordt de rechter indexwaarde midden − 1, wat gelijk is aan 6, en de linker indexwaarde blijft hetzelfde als voorheen, namelijk 5.
5. Op dit punt weet je dat 59 na 45 komt. Daarom wordt de linkerindex, die 5 is, ook midden.
6. 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 het volgende voorbeeld bekijken om te begrijpen hoe binair zoeken werkt.

1. Je hebt een reeks gesorteerde waarden variërend van 2 tot 20 en je moet 18 vinden.
2. Het gemiddelde van de onder- en bovengrens is (l + r) / 2 = 4. De gezochte waarde is groter dan het midden, dat 4 is.
3. Arraywaarden kleiner dan het midden worden uit de zoekopdracht verwijderd, en er wordt gezocht naar waarden groter dan het midden (4).
4. 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 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 vergelijkt de gesorteerde gegevens op basis van een ordeningsprincipe in plaats van gelijkheidsvergelijkingen, die trager en meestal onnauwkeurig zijn.
• Na elke zoekcyclus deelt het algoritme de grootte van de array in tweeën; in de volgende iteratie werkt het dus alleen met de resterende helft van de array.

Bekijk onze volgende tutorial over Lineair zoeken: Python, C++ Voorbeeld.

Binair zoeken versus lineair zoeken

Binair zoeken en lineair zoeken zijn de twee meest voorkomende manieren om een ​​waarde in een verzameling te vinden. De onderstaande tabel laat zien hoe ze van elkaar verschillen:

Kort gezegd is binair zoeken veel sneller bij grote, gesorteerde datasets, terwijl lineair zoeken eenvoudiger is en de enige optie wanneer de data niet gesorteerd is.

Veelgestelde vragen