როგორ მუშაობს ბინარული ძიების ალგორითმი?

ორმხრივი ძიება მუშაობს სორტირებულ მასივის ანალიზით და საძიებო ინტერვალის განმეორებით გაყოფით შუაზე.

1. დაწყება: საძიებო ინტერვალის მარცხენა და მარჯვენა საზღვრები განსაზღვრულია (საშუალოდ მასივის დასაწყისი და ბოლო).
2. შედარება: ინტერვალის შუა ინდექსი გამოითვლება. ამ ინდექსზე მყოფი მნიშვნელობა შედარებულია საძიებო ელემენტთან.
3. ინტერვალის შემცირება:
   • თუ შუა მნიშვნელობა ემთხვევა საძიებო ელემენტს, ელემენტი იპოვეს.
   • თუ შუა მნიშვნელობა მეტია საძიებო ელემენტზე, ძიება განახლდება ინტერვალის მარცხენა ნახევარში. მარჯვენა საზღვარი გადადის შუა - 1-ზე.
   • თუ შუა მნიშვნელობა ნაკლებია საძიებო ელემენტზე, ძიება განახლდება ინტერვალის მარჯვენა ნახევარში. მარცხენა საზღვარი გადადის შუა + 1-ზე.
4. გადავლის: ნაბიჯები 2 და 3 მეორდება, სანამ ელემენტი იპოვება ან ინტერვალი ცარიელია.

ალგორითმის სირთულე არის O(log n), რაც ბევრად უფრო ეფექტურია, ვიდრე ხაზოვანი ძიება დიდ მასივებზე.

Python-ის მაგალითი:

def binary_search(arr, target):
    """
    ორმხრივი ძიების განხორციელება.
    იღებს სორტირებულ მასივს და საძიებო მნიშვნელობას.
    აბრუნებს ელემენტის ინდექსს ან -1, თუ არ არის ნაპოვნი.
    """
    მარცხენა, მარჯვენა = 0, len(arr) - 1

    while მარცხენა <= მარჯვენა:
        შუა = (მარცხენა + მარჯვენა) // 2  # შუა ინდექსის გამოთვლა
        შუა_მნიშვნელობა = arr[შუა]      # შუა მნიშვნელობა

        if შუა_მნიშვნელობა == target:
            return შუა  # ელემენტი ნაპოვნია
        elif შუა_მნიშვნელობა < target:
            მარცხენა = შუა + 1  # ძიება მარჯვნივ
        else: # შუა_მნიშვნელობა > target
            მარჯვენა = შუა - 1 # ძიება მარცხნივ

    return -1 # ელემენტი არ არის ნაპოვნი