Welke algoritme heeft een logaritmische complexiteit O(log n)?

Het binaire zoekalgoritme (of dichotome zoekopdracht) heeft een logaritmische tijdscomplexiteit van O(log n).

Werking van binair zoeken:

1. Vereist een gesorteerde array (of lijst).
2. Vergelijkt bij elke stap het gezochte element met het element in het midden van het huidige zoekbereik.
3. Als de elementen overeenkomen, is de zoekopdracht voltooid.
4. Als het gezochte element kleiner is dan het midden, wordt de zoekopdracht voortgezet in de linkerhelft.
5. Als het gezochte element groter is dan het midden, wordt de zoekopdracht voortgezet in de rechterhelft.
6. Het zoekbereik wordt bij elke stap gehalveerd.

Voorbeeld van implementatie in Python:

# Functie voor binaire zoekopdracht
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        mid_val = arr[mid]

        if mid_val == target:
            return mid  # Element gevonden, retourneer index
        elif mid_val < target:
            low = mid + 1  # Negeer linker helft
        else:
            high = mid - 1  # Negeer rechter helft

    return -1  # Element niet gevonden

# Voorbeeld van gebruik
# gesorteerde_lijst = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# doelwaarde = 23
# resultaat = binary_search(gesorteerde_lijst, doelwaarde)
# if resultaat != -1:
#     print(f"Element gevonden op index: {resultaat}")
# else:
#     print("Element niet gevonden")

De logaritmische complexiteit komt doordat het aantal bewerkingen evenredig is met de logaritme van de invoerdata (n), omdat bij elke stap de zoekruimte wordt gehalveerd.