Кадом алгоритм дорои мураккабияти логарифмикӣ 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("Унсур ёфт нашуд")

Мураккабии логарифмик ба он вобаста аст, ки шумораи амалҳо ба логарифми андозаи маълумотҳои воридотӣ (n) мувофиқ аст, зеро дар ҳар қадам майдони ҷустуҷӯ ба нимӣ кам мешавад.