Milline algoritm omab logaritmilist keerukust O(log n)?

Binaarse otsingu algoritm (või dikotomiline otsing) omab logaritmilist ajakulu O(log n).

Binaarse otsingu põhimõte:

1. Vajalik on sorteeritud massiiv (või nimekiri).
2. Iga sammu jooksul võrdleb otsitavat elementi praeguse otsingupiirkonna keskpunkti elemendiga.
3. Kui elemendid kattuvad, lõpeb otsing.
4. Kui otsitav element on väiksem kui keskne, jätkub otsing vasakul poolel.
5. Kui suurem, jätkub otsing paremal poolel.
6. Otsingupiirkond väheneb iga sammu jooksul poole võrra.

Python näide:

# Binaarse otsingu funktsioon
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  # Element leitud, tagastab indeksi
        elif mid_val < target:
            low = mid + 1  # Ignoreerib vasakut poolt
        else:
            high = mid - 1  # Ignoreerib paremat poolt

    return -1  # Elementi ei leitud

# Kasutamise näide
# sorteeritud_nimekiri = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# eesmärk = 23
# tulemus = binary_search(sorteeritud_nimekiri, eesmärk)
# if tulemus != -1:
#     print(f"Element leiti indeksil: {tulemus}")
# else:
#     print("Elementi ei leitud")

Logaritmiline keerukus tuleneb sellest, et operatsioonide arv on proportsionaalne logaritmiga sisendandmete suurusest (n), kuna iga sammu jooksul otsinguala väheneb poole võrra.