बाइनरी सर्च एक खोज एल्गोरिदम है जो तत्व की तुलना ऐरे के मध्य मान से करके और मान के आधार पर इसे विभाजित करके तत्व को खोजता है। एल्गोरिदम इसे तब तक दोहराता है जब तक तत्व न मिल जाए।
बाइनरी सर्च लागू करने के लिए ऐरे का सॉर्टेड होना आवश्यक है।
बाइनरी सर्च की समय जटिलता लॉगरिदमिक क्रम की होती है। इसलिए प्रोग्रामर्स के लिए इसके कार्यान्वयन के साथ-साथ बाइनरी सर्च से संबंधित शॉर्टहैंड जानना बहुत महत्वपूर्ण है ताकि एल्गोरिदम को कोड करने में लगने वाला समय कम हो सके। स्टैंडर्ड टेम्पलेट लाइब्रेरी (STL) में शामिल बाइनरी सर्च एल्गोरिदम से संबंधित फ़ंक्शन्स यहां चर्चा की गई हैं।
lower_bound
lower_bound - लोअर बाउंड सर्च वह स्थिति लौटाता है जहां तत्व पाया जाता है।
सिंटैक्स
lower_bound(start_pointer, end_pointer, element)
यहां,
start_pointer वह पॉइंटर है जो खोज संरचना के प्रारंभिक बिंदु की मेमोरी लोकेशन रखता है।
end_pointer वह पॉइंटर है जो खोज संरचना के अंतिम बिंदु की मेमोरी लोकेशन रखता है।
element वह तत्व है जिसे फ़ंक्शन का उपयोग करके ढूंढा जाना है।
फ़ंक्शन उस तत्व का इंडेक्स लौटाता है जिसे ढूंढा जाना है।
रिटर्न मान कई मान ले सकता है:
- यदि तत्व संरचना में एक बार आता है, तो स्थिति लौटाई जाती है।
- यदि तत्व संरचना में एक से अधिक बार आता है, तो पहले तत्व की स्थिति लौटाई जाती है।
- यदि तत्व संरचना में नहीं आता है, तो तत्व से अगली उच्च संख्या की स्थिति लौटाई जाती है।
किसी भी तत्व का इंडेक्स संरचना के बेस पोजीशन को घटाकर पाया जाता है।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> sortedarray = {2, 5, 7, 8, 15, 20};
vector<int> sortedarray2 = {2, 3, 4, 6, 9, 23};
vector<int> sortedarray3 = {2, 5, 7, 7, 15, 20};
cout << "The position of element 7 found using lower_bound function:";
cout << "\nCase 1: When element is present in array but only once";
cout << lower_bound(sortedarray.begin(), sortedarray.end(), 7) - sortedarray.begin();
cout << "\nCase 2: When element is present more than one times in the array";
cout << lower_bound(sortedarray3.begin(), sortedarray3.end(), 7) - sortedarray3.begin();
cout << "\nCase 3: When element is not present in the array";
cout << lower_bound(sortedarray2.begin(), sortedarray2.end(), 7) - sortedarray2.begin();
}
आउटपुट
The position of element 7 found using lower_bound function: Case 1: When element is present in array but only once 2 Case 2: When element is present more than one times in the array 2 Case 3: When element is not present in the array 4
upper_bound
upper_bound - अपर बाउंड सर्च पास किए गए तत्व से बड़े तत्व की स्थिति लौटाता है।
सिंटैक्स
upper_bound(start_pointer, end_pointer, element)
यहां,
start_pointer खोज संरचना के प्रारंभिक बिंदु की मेमोरी लोकेशन रखने वाला पॉइंटर है।
end_pointer खोज संरचना के अंतिम बिंदु की मेमोरी लोकेशन रखने वाला पॉइंटर है।
element वह तत्व है जिसे फ़ंक्शन का उपयोग करके ढूंढा जाना है।
फ़ंक्शन उस तत्व का इंडेक्स लौटाता है जिसका मान पास किए गए तत्व के मान से बड़ा है।
रिटर्न मान कई मान ले सकता है:
- यदि तत्व संरचना में एक बार आता है, तो अगले उच्च तत्व की स्थिति लौटाई जाती है।
- यदि तत्व संरचना में एक से अधिक बार आता है, तो अंतिम तत्व के अगले तत्व की स्थिति लौटाई जाती है।
- यदि तत्व संरचना में नहीं आता है, तो तत्व से अगली उच्च संख्या की स्थिति लौटाई जाती है।
किसी भी तत्व का इंडेक्स संरचना के बेस पोजीशन को घटाकर पाया जाता है।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> sortedarray = {2, 5, 7, 8, 15, 20};
vector<int> sortedarray2 = {2, 3, 4, 6, 9, 23};
vector<int> sortedarray3 = {2, 5, 7, 7, 15, 20};
cout << "The position of element 7 found using upper_bound function:";
cout << "\nCase 1: When element is present in array but only once";
cout << upper_bound(sortedarray.begin(), sortedarray.end(), 7) - sortedarray.begin();
cout << "\nCase 2: When element is present more than one times in the array";
cout << upper_bound(sortedarray3.begin(), sortedarray3.end(), 7) - sortedarray3.begin();
cout << "\nCase 3: When element is not present in the array";
cout << upper_bound(sortedarray2.begin(), sortedarray2.end(), 7) - sortedarray2.begin();
}
आउटपुट
The position of element 7 found using upper_bound function: Case 1: When element is present in array but only once 3 Case 2: When element is present more than one times in the array 4 Case 3: When element is not present in the array 4
binary_search
binary_search एक फ़ंक्शन है जो जांचता है कि तत्व संरचना में मौजूद है या नहीं।
सिंटैक्स
binary_search(start_pointer, end_pointer, element)
यहां,
start_pointer खोज संरचना के प्रारंभिक बिंदु की मेमोरी लोकेशन रखने वाला पॉइंटर है।
end_pointer खोज संरचना के अंतिम बिंदु की मेमोरी लोकेशन रखने वाला पॉइंटर है।
element वह तत्व है जिसे फ़ंक्शन का उपयोग करके ढूंढा जाना है।
यदि तत्व संरचना में मौजूद है, तो फ़ंक्शन true लौटाता है। अन्यथा, यह false लौटाता है।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> sortedarray = {6, 15, 21, 27, 39, 42};
cout << "The element to be found in the array is 21\n";
if (binary_search(sortedarray.begin(), sortedarray.end(), 21))
cout << "The element is found";
else
cout << "The element is not found";
cout << "\nThe element to be found in the array is 5\n";
if (binary_search(sortedarray.begin(), sortedarray.end(), 5))
cout << "The element is found";
else
cout << "The element is not found";
}
आउटपुट
The element to be found in the array is 21 The element is found The element to be found in the array is 5 The element is not found
