Որ ալգորիթմը ունի լոգարիթմական բարդություն 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), քանի որ յուրաքանչյուր քայլում որոնման տարածքը կիսվում է կեսով: