Melyik algoritmus rendelkezik logaritmikus komplexitással, azaz O(log n)?

A bináris keresési algoritmus (vagy dikotomikus keresés) logaritmikus időkomplexitással rendelkezik O(log n).

A bináris keresés működési elve:

1. Szükség van egy rendezett tömbre (vagy listára).
2. Minden lépésben összehasonlítja a keresett elemet a jelenlegi keresési tartomány közepén lévő elemmel.
3. Ha az elemek egyeznek, a keresés befejeződik.
4. Ha a keresett elem kisebb, mint a középső, a keresés a tartomány bal felében folytatódik.
5. Ha a keresett elem nagyobb, mint a középső, a keresés a tartomány jobb felében folytatódik.
6. A keresési tartomány minden lépésben a felére csökken.

Python példakód:

# Bináris kereső függvény
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  # Elem megtalálva, index visszaadása
        elif mid_val < target:
            low = mid + 1  # Bal felét figyelmen kívül hagyja
        else:
            high = mid - 1  # Jobb felét figyelmen kívül hagyja

    return -1  # Elem nem található

# Használati példa
# rendezett_lista = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# cél = 23
# eredmény = binary_search(rendezett_lista, cél)
# if eredmény != -1:
#     print(f"Elem megtalálva a indexen: {eredmény}")
# else:
#     print("Elem nem található")

A logaritmikus komplexitás abból adódik, hogy az műveletek száma arányos a bemeneti adatok számának logaritmusával (n), mivel minden lépésben a keresési tartomány feleződik.