Kura algoritma ir logaritmiskā sarežģītība O(log n)?

Binārās meklēšanas algoritms (vai dikotomiskā meklēšana) ir logaritmiskas laika sarežģītības O(log n).

Binārās meklēšanas princips:

1. Prasība ir sakārtots masīvs (vai saraksts).
2. Katrs solis salīdzina meklēto elementu ar elementu pašā vidū esošo elementu pašreizējā meklēšanas diapazonā.
3. Ja elementi sakrīt, meklēšana beidzas.
4. Ja meklētais elements ir mazāks par vidējo, turpina kreisajā pusē.
5. Ja lielāks, turpina labajā pusē.
6. Meklēšanas diapazons katrā solī tiek samazināts uz pusi.

Python piemērs:

# Binārās meklēšanas 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  # Elements atrod, atgriež indeksu
        elif mid_val < target:
            low = mid + 1  # Ignorē kreiso pusi
        else:
            high = mid - 1  # Ignorē labo pusi

    return -1  # Elements nav atrasts

# Piemērs izmantošanai
# sakārtots_saraksts = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# mērķis = 23
# rezultāts = binary_search(sakārtots_saraksts, mērķis)
# if rezultāts != -1:
#     print(f"Elements atrodas indeksā: {rezultāts}")
# else:
#     print("Elements nav atrasts")

Logaritmiskā sarežģītība ir saistīta ar to, ka operāciju skaits ir proporcionāls logaritmam no ievades datu lieluma (n), jo katrā solī meklēšanas apjoms tiek samazināts uz pusi.