सी में एक कुशल बाइनरी खोज एल्गोरिदम की खोज

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

सी मानक लाइब्रेरी हेडर में std::binary_search प्रदान करती है, लेकिन यह एक बूलियन लौटाता है। जैसा कि प्रश्नकर्ता ने नोट किया है, यह उन स्थितियों के लिए निराशाजनक हो सकता है जहां बाइनरी खोज की गति वांछित है और डेटा को सॉर्ट करने के लिए जाना जाता है।

सौभाग्य से, ऐसे वैकल्पिक कार्यान्वयन उपलब्ध हैं जो वांछित कार्यक्षमता प्रदान करते हैं। एक लोकप्रिय विकल्प एक कस्टम एल्गोरिदम का उपयोग करना है जो std::lower_ound, std::upper_ound, या std::equal_range फ़ंक्शंस का लाभ उठाता है। इस तरह के कार्यान्वयन का एक सरलीकृत संस्करण यहां दिया गया है:

template
Iter binary_find(Iter begin, Iter end, T val) {
    // Determine the lower bound using binary search
    Iter i = std::lower_bound(begin, end, val);

    // If the element is found, return the iterator to it
    if (i != end && !(val 
वैकल्पिक रूप से, एक std::set का उपयोग किया जा सकता है, जो तत्वों के क्रम की गारंटी देता है और खोज विधि प्रदान करता है जो वांछित आइटम पर एक पुनरावर्तक लौटाता है। हालाँकि, यह विचार करना महत्वपूर्ण है कि क्या आवश्यकताएँ किसी सेट के उपयोग के अनुकूल हैं, खासकर उन मामलों में जहां एक ही तत्व के कई उदाहरणों को संग्रहीत करने की आवश्यकता होती है।