बाइनरी सर्च एक खोज एल्गोरिदम है जो सॉर्टेड ऐरे के भीतर लक्ष्य मान की स्थिति ढूंढता है। बाइनरी सर्च लक्ष्य मान की तुलना सॉर्टेड ऐरे के मध्य तत्व से करता है। बाइनरी सर्च की समय जटिलता O(log n) है। यह एक C++ प्रोग्राम है जिसमें हम C++ STL में विभिन्न बाइनरी सर्च फंक्शन को लागू करते हैं।
एल्गोरिदम
Begin
पूर्णांक मानों के वेक्टर को इनिशियलाइज़ करें।
यहां उपयोग किए गए फंक्शन हैं:
binary_search(start_pointer, end_pointer, value) = यदि मान ऐरे में मौजूद है तो true लौटाता है अन्यथा false।
lower_bound(start_pointer, end_pointer, value) = "मान की स्थिति" का पॉइंटर लौटाता है यदि कंटेनर में मान का 1 occurrence है। "मान की पहली स्थिति" का पॉइंटर लौटाता है यदि कंटेनर में मान के एकाधिक occurrence हैं। "मान से अगली बड़ी संख्या की स्थिति" का पॉइंटर लौटाता है यदि कंटेनर में मान का कोई occurrence नहीं है।
upper_bound(start_pointer, end_pointer, value) = "मान से अगले बड़े मान की स्थिति" का पॉइंटर लौटाता है यदि कंटेनर में मान का 1 occurrence है। "मान के अंतिम occurrence से अगली बड़ी संख्या की पहली स्थिति" का पॉइंटर लौटाता है यदि कंटेनर में मान के एकाधिक occurrence हैं। "मान से अगली बड़ी संख्या की स्थिति" का पॉइंटर लौटाता है यदि कंटेनर में मान का कोई occurrence नहीं है।
परिणाम प्रिंट करें।
End.
उदाहरण कोड
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> a = {6, 7, 10, 14, 16, 20};
if (binary_search(a.begin(), a.end(), 50))
cout << "50 exists in vector";
else
cout << "50 does not exist";
cout << endl;
if (binary_search(a.begin(), a.end(), 7))
cout << "7 exists in the vector";
else
cout << "7 does not exist";
cout << endl;
cout << "The position of 7 using lower_bound ";
cout << lower_bound(a.begin(), a.end(), 7) - a.begin();
cout << endl;
cout << "The position of 7 using upper_bound ";
cout << upper_bound(a.begin(), a.end(), 7) - a.begin();
cout << endl;
}
आउटपुट
50 does not exist
7 exists in the vector
The position of 7 using lower_bound 1
The position of 7 using upper_bound 2
