Кай алгоритм логарифмикалык татаалдыкка ээ, яъни 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("Элемент табылган жок")

Логарифмик татаалдыгы, иштетилген операциялар саны, киргизилген маалыматтын өлчөмүнүн логарифми менен пропорционалдуу, анткени ар бир кадамда издөөнүн кеңейиши жарымына кыскартыла берет.