ბინარული ძიების (Binary Search) ალგორითმი C++-ში- ახსნა, მაგალითი და კოდი

ბინარული ძიების ალგორითმი არის უფრო ეფექტური გზა კონკრეტული ელემენტის მოსაძებნად დახარისხებულ სიაში. ხაზოვანი ძიებისგან განსხვავებით, რომელიც ამოწმებს ელემენტებს თანმიმდევრულად, ორობითი ძიება ყოფს სიას ნახევრად და ადარებს სამიზნე ელემენტს შუა ელემენტთან. ეს პროცესი მეორდება მანამ, სანამ სამიზნე ელემენტი არ მოიძებნება ან საძიებო დიაპაზონი ცარიელი არ გახდება.

Როგორ მუშაობს

1. დაიწყეთ მთელი დალაგებული სიით.
2. იპოვეთ მიმდინარე საძიებო დიაპაზონის შუა ელემენტი.
3. შეადარეთ შუა ელემენტი სამიზნე მნიშვნელობას.
4. თუ შუა ელემენტი უდრის სამიზნე მნიშვნელობას, ძიება წარმატებულია.
5. თუ შუა ელემენტი სამიზნეზე მეტია, მოძებნეთ დიაპაზონის მარცხენა ნახევარში.
6. თუ შუა ელემენტი სამიზნეზე მცირეა, მოძებნეთ დიაპაზონის მარჯვენა ნახევარში.
7. გაიმეორეთ ნაბიჯები 2-6, სანამ არ მოიძებნება სამიზნე ელემენტი ან ძიების დიაპაზონი ცარიელი არ გახდება.

მაგალითი

მოდით განვიხილოთ მთელი რიცხვების დალაგებული სია და გვინდა ვიპოვოთ რიცხვი 34 ბინარული ძიების გამოყენებით.

დალაგებული სია: {12, 23, 34, 45, 56, 67, 89, 90}

1. დაიწყეთ მთელი სიით.
2. შუა ელემენტი: 56(პოზიცია 4). შეადარე 34-ს.
3. 56 მეტია 34-ზე. ძიება მარცხენა ნახევარში.
4. ახალი შუა ელემენტი: 23(პოზიცია 1). შეადარე 34-ს.
5. 23 34-ზე პატარაა. მოძებნეთ მარჯვენა ნახევარში.
6. ახალი შუა ელემენტი: 45(პოზიცია 3). შეადარე 34-ს.
7. 45 მეტია 34-ზე. ძიება მარცხენა ნახევარში.
8. ახალი შუა ელემენტი: 34(პოზიცია 2). სამიზნე ნაპოვნია.

კოდის მაგალითი C++-ში

#include <iostream>  
#include <vector>  
  
int binarySearch(const std::vector<int>& arr, int target) {  
    int left = 0;  
    int right = arr.size()- 1;  
  
    while(left <= right) {  
        int mid = left +(right- left) / 2;  
  
        if(arr[mid] == target) {  
            return mid;  
        } else if(arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid- 1;  
        }  
    }  
  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 23, 34, 45, 56, 67, 89, 90};  
    int target = 34;  
  
    int result = binarySearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}  

მოცემულ მაგალითში binarySearch ფუნქცია გამოიყენება მთელი რიცხვების დალაგებულ სიაში 34-ის საპოვნელად. შედეგი იქნება 34-ის პოზიცია სიაში(პოზიციები იწყება 0-დან) ან -1, თუ რიცხვი ვერ მოიძებნა.