Hangi algoritmanın zaman karmaşıklığı O(log n) olan logaritmik bir algoritmadır?

İkili arama algoritması (veya dikotomik arama) logaritmik zaman karmaşıklığına sahiptir O(log n).

İkili arama prensibi:

1. Sıralanmış bir diziye (veya listeye) ihtiyaç duyar.
2. Her adımda, aranan öğeyi, mevcut arama aralığının ortasındaki öğeyle karşılaştırır.
3. Öğeler eşleşiyorsa, arama sona erer.
4. Aranan öğe ortadan küçükse, arama sol yarıda devam eder.
5. Aranan öğe ortadan büyükse, arama sağ yarıda devam eder.
6. Arama aralığı her adımda yarıya indirilir.

Python'da bir örnek uygulama:

# İkili arama fonksiyonu
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  # Öğe bulundu, indeksi döndürür
        elif mid_val < target:
            low = mid + 1  # Sol yarıyı görmezden gelir
        else:
            high = mid - 1  # Sağ yarıyı görmezden gelir

    return -1  # Öğe bulunamadı

# Kullanım örneği
# sıralı_list = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# hedef_değer = 23
# sonuç = binary_search(sıralı_list, hedef_değer)
# if sonuç != -1:
#     print(f"Öğe indeksinde bulundu: {sonuç}")
# else:
#     print("Öğe bulunamadı")

Logaritmik karmaşıklık, giriş verilerinin boyutunun logaritmasıyla orantılı olan işlem sayısından kaynaklanır, çünkü her adımda arama alanı yarıya indirilir.