C++ में बाइनरी सर्च (Binary Search) एल्गोरिथम- स्पष्टीकरण, उदाहरण और कोड

बाइनरी सर्च एल्गोरिदम क्रमबद्ध सूची में किसी विशिष्ट तत्व को खोजने का एक अधिक कुशल तरीका है। रैखिक खोज के विपरीत, जो तत्वों को क्रमिक रूप से जांचता है, बाइनरी खोज सूची को आधे में विभाजित करती है और लक्ष्य तत्व की तुलना मध्य तत्व से करती है। यह प्रक्रिया तब तक दोहराई जाती है जब तक लक्ष्य तत्व नहीं मिल जाता या खोज सीमा खाली नहीं हो जाती।

यह काम किस प्रकार करता है

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 यदि संख्या नहीं मिली है।