द्विआधारी खोज एक खोज एल्गोरिथम है जो किसी तत्व को सरणी के मध्य मान से तुलना करके और मान के आधार पर विभाजित करके उसकी खोज करता है। एल्गोरिथम ऐसा तब तक बार-बार करता है जब तक कि तत्व नहीं मिल जाता।
सरणी को एक बाइनरी खोज लागू करने के लिए क्रमबद्ध किया जाना चाहिए।
द्विआधारी खोज की समय जटिलता लघुगणक . की है गण। इसलिए प्रोग्रामर के लिए एल्गोरिथम को कोड करने के लिए समय को कम करने के लिए इसके कार्यान्वयन के साथ-साथ बाइनरी सर्च से संबंधित शॉर्टहैंड को जानना बहुत महत्वपूर्ण है। मानक टेम्पलेट लाइब्रेरी (एसटीएल) में शामिल बाइनरी सर्च एल्गोरिथम से संबंधित कार्यों पर यहां चर्चा की गई है।
निचला_बाउंड -निचली बाध्य खोज उस स्थिति को लौटाती है जहां तत्व पाया जाता है।
सिंटैक्स
lower_bound(start_pointer , end_pointer, element )
यहाँ,
प्रारंभ_सूचक वह सूचक है जो खोज संरचना के शुरुआती बिंदु की स्मृति स्थान रखता है।
end_pointer एक सूचक है जो खोज संरचना के समापन बिंदु की स्मृति स्थान रखता है।
तत्व वह तत्व है जो फ़ंक्शन का उपयोग करके पाया जाना है।
फ़ंक्शन उस तत्व की अनुक्रमणिका देता है जिसे ढूँढना है।
रिटर्न वैल्यू में कई मान हो सकते हैं -
यदि तत्व संरचना में एक बार होता है, तो स्थिति वापस आ जाती है।
यदि तत्व संरचना में एक से अधिक बार आता है, तो पहले तत्व की स्थिति वापस आ जाती है।
यदि संरचना में तत्व नहीं होता है, तो तत्व की तुलना में अगली उच्च संख्या की स्थिति वापस आ जाती है।
सूचकांक संरचना की आधार स्थिति को घटाकर किसी भी तत्व का पता लगाया जाता है।
उदाहरण
#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(start_pointer , end_pointer, element)
यहाँ,
प्रारंभ_सूचक वह सूचक है जो खोज संरचना के शुरुआती बिंदु की स्मृति स्थान रखता है।
end_pointer एक सूचक है जो खोज संरचना के समापन बिंदु की स्मृति स्थान रखता है।
तत्व वह तत्व है जो फ़ंक्शन का उपयोग करके पाया जाना है।
फ़ंक्शन उस तत्व की अनुक्रमणिका देता है जिसका मान तत्व के मान से अधिक है।
रिटर्न वैल्यू में कई मान हो सकते हैं -
यदि तत्व संरचना में एक बार आता है, तो अगले उच्च तत्व की स्थिति लौटा दी जाती है।
यदि तत्व संरचना में एक से अधिक बार होता है, तो अंतिम तत्व के अगले तत्व की स्थिति वापस आ जाती है।
यदि संरचना में तत्व नहीं होता है, तो तत्व की तुलना में अगले उच्च संख्या की स्थिति वापस आ जाती है।
सूचकांक संरचना की आधार स्थिति को घटाकर किसी भी तत्व का पता लगाया जाता है।
उदाहरण
#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(start_pointer , end_pointer, element)
यहाँ,
प्रारंभ_सूचक वह सूचक है जो खोज संरचना के शुरुआती बिंदु की स्मृति स्थान रखता है।
end_pointer एक सूचक है जो खोज संरचना के समापन बिंदु की स्मृति स्थान रखता है।
तत्व वह तत्व है जो फ़ंक्शन का उपयोग करके पाया जाना है।
यदि तत्व संरचना में मौजूद है, तो फ़ंक्शन सही हो जाता है। अन्यथा, यह झूठी वापसी करेगा।
उदाहरण
#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