Qaysi algoritm logaritimik murakkablikka ega, ya'ni O(log n)?

Бинар излаш алгоритми (ёки иккиламчи излаш) логарифмик вақт мураккаблигига эга O(log n).

Бинар излаш принципи:

1. Тартибланган массив (ёки рўйхат) талаб қилади.
2. Ҳар қадамда, изланмоқчи бўлган элементни ҳозирги излаш диапазининг ўртадаги элемент билан солиштиради.
3. Агар элементлар мос келса, излаш тугайди.
4. Агар изланмоқчи бўлган элемент ўртадан кичик бўлса, излаш ўнг яримда давом этади.
5. Агар изланмоқчи бўлган элемент ўртадан катта бўлса, излаш чап яримда давом этади.
6. Излаш диапазини ҳар қадамда иккига бўлади.

Pythonда мисол:

# Бинар излаш функцияси
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  # Элемент топилди, индекс қайтарилади
        elif mid_val < target:
            low = mid + 1  # Чап яримни игнор қилади
        else:
            high = mid - 1  # Ўнг яримни игнор қилади

    return -1  # Элемент топилмади

# Ишлатиш мисоли
# тартибланган_рўйхат = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# мақсад_қиймат = 23
# натижа = binary_search(тартибланган_рўйхат, мақсад_қиймат)
# if натижа != -1:
#     print(f"Элемент топилди индексда: {нәтижа}")
# else:
#     print("Элемент топилмади")

Логарифмик мураккаблик, кириш маълумотларининг ҳажмининг логарифми билан тўғри келади, чунки ҳар қадамда излаш майдони яримга бўлинади.