Hoe werkt het binaire zoekalgoritme?

Binaire zoekopdracht werkt door een gesorteerde array te analyseren en het zoekinterval herhaaldelijk in twee te delen.

1. Initialisatie: Bepaal de linker- en rechtergrens van het zoekinterval (meestal het begin en het einde van de array).
2. Vergelijking: Bereken de index van het midden van het interval. De waarde op die index wordt vergeleken met het gezochte element.
3. Verkleining van het interval:
   • Als de waarde in het midden overeenkomt met de gezochte, is het element gevonden.
   • Als de waarde in het midden groter is dan de gezochte, gaat de zoekopdracht verder in de linkerhelft van het interval. De rechtergrens verschuift naar midden - 1.
   • Als de waarde in het midden kleiner is dan de gezochte, gaat de zoekopdracht verder in de rechterhelft van het interval. De linkergrens verschuift naar midden + 1.
4. Herhaling: De stappen 2 en 3 worden herhaald totdat het element wordt gevonden of het zoekinterval leeg is.

De complexiteit van het algoritme is O(log n), wat veel efficiënter is dan lineair zoeken voor grote arrays.

Voorbeeld van implementatie in Python:

def binary_search(arr, target):
    """
    Implementatie van binaire zoekopdracht.
    Neemt een gesorteerde array en de gezochte waarde.
    Retourneert de index van het element of -1 als het niet wordt gevonden.
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # Berekening van de middelindex
        mid_val = arr[mid]      # Waarde in het midden

        if mid_val == target:
            return mid  # Element gevonden
        elif mid_val < target:
            left = mid + 1  # Zoeken rechts
        else: # mid_val > target
            right = mid - 1 # Zoeken links

    return -1 # Element niet gevonden