Hansı algoritm logaritmik mürəkkəbliyə malikdir, yəni O(log n)?

İkili axtarış alqoritmi (və ya dikotom axtarış) logaritmik vaxt mürəkkəbliyinə malikdir O(log n).

İkili axtarış prinsipi:

1. Tərtib olunmuş massiv (və ya siyahı) tələb edir.
2. Hər addımda, axtarılan elementi cari axtarış diapazonunun ortasındakı elementlə müqayisə edir.
3. Əgər elementlər uyğun gəlirsə, axtarış tamamlanır.
4. Əgər axtarılan element ortadan kiçikdirsə, axtarış sol yarımda davam edir.
5. Əgər axtarılan element ortadan böyükdürsə, axtarış sağ yarımda davam edir.
6. Axtarış diapazonu hər addımda yarıya endirilir.

Python-da nümunə tətbiq:

# İkili axtarış funksiyası
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 tapıldı, indeks qaytarılır
        elif mid_val < target:
            low = mid + 1  # Sol yarımı nəzərə almır
        else:
            high = mid - 1  # Sağ yarımı nəzərə almır

    return -1  # Element tapılmadı

# İstifadə nümunəsi
# sıralanmış_liste = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# məqsəd = 23
# nəticə = binary_search(sıralanmış_liste, məqsəd)
# if nəticə != -1:
#     print(f"Element tapıldı indeksdə: {nəticə}")
# else:
#     print("Element tapılmadı")

Logaritmik mürəkkəblik, əməliyyatların sayının giriş məlumatlarının ölçüsünün logaritmiyə uyğun olmasından irəli gəlir, çünki hər addımda axtarış sahəsi yarıya endirilir.