რომელი ალგორითმი აქვს ლოგარითმული სირთულე 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), რადგან ყოველი ნაბიჯით ძიების სივრცე ნახევარით მცირდება.