close

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 क्रमांक आढळला नाही तर.