Kuris algoritmas turi logaritminę sudėtingumą O(log n)?

Dvinarių paieškos algoritmas (arba dikotominis paieška) turi logaritminę laiko sudėtingumą O(log n).

Dvinarių paieškos principas:

1. Reikalauja surūšiuoto masyvo (arba sąrašo).
2. Kiekviename žingsnyje lygina ieškomą elementą su elemento viduryje esamu elementu.
3. Jei elementai sutampa, paieška baigiama.
4. Jei ieškomas elementas yra mažesnis už vidurį, tęsiasi kairėje pusėje.
5. Jei didesnis, tęsiasi dešinėje pusėje.
6. Paieškos diapazonas kiekviename žingsnyje sumažėja perpus.

Python pavyzdys:

# Dvinarių paieškos funkcija
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  # Elementas rastas, grąžina indeksą
        elif mid_val < target:
            low = mid + 1  # Ignoruoja kairę pusę
        else:
            high = mid - 1  # Ignoruoja dešinę pusę

    return -1  # Elementas nerastas

# Pavyzdys naudojimo
# surūšiuotas_sarasas = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# tikslas = 23
# rezultatas = binary_search(surūšiuotas_sarasas, tikslas)
# if rezultatas != -1:
#     print(f"Elementas rastas indeksu: {rezultatas}")
# else:
#     print("Elementas nerastas")

Logaritminė sudėtingumas kyla dėl to, kad operacijų skaičius yra proporcingas logaritmui iš įvesties duomenų dydžio (n), nes kiekviename žingsnyje paieškos plotas sumažėja perpus.