(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।