कंप्यूटर विज्ञान में सबसे मौलिक एल्गोरिदम में से एक बाइनरी सर्च एल्गोरिदम है। आप दो विधियों का उपयोग करके बाइनरी खोज को लागू कर सकते हैं: पुनरावृत्ति विधि और पुनरावर्ती विधि। जबकि दोनों विधियों में एक ही समय की जटिलता है, पुनरावृत्त विधि अंतरिक्ष जटिलता के मामले में अधिक कुशल है।
पुनरावृत्त विधि की एक अंतरिक्ष जटिलता है हे (1) इसकी तुलना में ओ (लॉगिन) पुनरावर्ती विधि द्वारा निर्मित। तो, आप सी, सी++, और पायथन में पुनरावृत्त विधि का उपयोग करके बाइनरी सर्च एल्गोरिदम को कैसे कार्यान्वित कर सकते हैं?
बाइनरी सर्च क्या है?
बाइनरी सर्च, जिसे हाफ-इंटरवल सर्च, लॉगरिदमिक सर्च या बाइनरी चॉप के रूप में भी जाना जाता है, एक एल्गोरिथम है जो सॉर्ट किए गए एरे में किसी तत्व की स्थिति को खोजता है और लौटाता है। खोज तत्व की तुलना मध्य तत्व से की जाती है। निचली और ऊपरी सीमाओं का औसत निकालकर, आप मध्य तत्वों को पा सकते हैं।
यदि खोज तत्व मध्य तत्व से बड़ा है, तो इसका अर्थ है कि बाईं ओर के सभी तत्व खोज तत्व से छोटे हैं। इसलिए, निचली सीमा को मध्य तत्व की अगली स्थिति तक बढ़ाकर नियंत्रण सरणी के दाईं ओर स्थानांतरित हो जाता है (यदि सरणी आरोही क्रम में है)।
इसी तरह, यदि खोज तत्व मध्य तत्व से छोटा है, तो इसका अर्थ है कि दाईं ओर के सभी तत्व खोज तत्व से बड़े हैं। इसलिए, नियंत्रण ऊपरी सीमा को मध्य तत्व की पिछली स्थिति में बदलकर सरणी के बाएं हिस्से में स्थानांतरित हो जाता है।
यह तुलना की तुलना में तुलना की संख्या को काफी कम कर देता है रैखिक खोज कार्यान्वयन जहां तुलना की संख्या सबसे खराब स्थिति में तत्वों की संख्या के बराबर होती है। फोनबुक में नंबर या डिक्शनरी में शब्द खोजने के लिए यह तरीका बहुत उपयोगी साबित होता है।
यहाँ का आरेखीय प्रतिनिधित्व है बाइनरी सर्च एल्गोरिथम:
सी का उपयोग करके बाइनरी खोज
सी का उपयोग कर बाइनरी खोज को लागू करने के लिए इन चरणों का पालन करें:
इसमें C, C++, Java और Python का उपयोग करने वाले बाइनरी सर्च प्रोग्राम का पूरा सोर्स कोड मौजूद है गिटहब रिपॉजिटरी.
कार्यक्रम एक समारोह को परिभाषित करता है, द्विआधारी खोज(), जो या तो मिले मूल्य का सूचकांक लौटाता है या -1 अगर यह मौजूद नहीं है:
#शामिल करना <stdio.h>
int यहाँद्विआधारी खोज(int यहाँ आगमन [], int यहाँ आगमन_आकार, int यहाँ search_number){
/*... */
}
फ़ंक्शन खोज स्थान को पुनरावृत्त रूप से कम करके काम करता है। चूंकि बाइनरी सर्च सॉर्ट किए गए सरणियों पर काम करता है, आप मध्य की गणना कर सकते हैं जो अन्यथा समझ में नहीं आता है। आप या तो उपयोगकर्ता से एक क्रमबद्ध सरणी के लिए पूछ सकते हैं या सॉर्टिंग एल्गोरिदम जैसे बबल या चयन सॉर्ट का उपयोग कर सकते हैं।
कम और उच्च वेरिएबल्स इंडेक्स को स्टोर करते हैं जो वर्तमान खोज स्थान की सीमाओं का प्रतिनिधित्व करते हैं। मध्य इंडेक्स को बीच में स्टोर करता है:
int यहाँ कम = 0, उच्च = arr_size - 1, मध्य;मुख्य जबकि() लूप खोज स्थान को कम कर देगा। यदि निम्न सूचकांक का मान कभी भी उच्च सूचकांक से अधिक हो जाता है, तो खोज स्थान समाप्त हो गया है, इसलिए मान मौजूद नहीं हो सकता।
जबकि (निम्न <= उच्च) {
/* कायम है... [1] */
}
वापस करना-1;
लूप की शुरुआत में मिडपॉइंट को अपडेट करने के बाद, तीन संभावित परिणाम हैं:
- यदि मध्य बिंदु पर वह मान है जिसकी हम तलाश कर रहे हैं, तो उस सूचकांक को लौटा दें।
- यदि मध्यबिंदु मान हमारे द्वारा खोजे जा रहे मान से अधिक है, तो उच्च को कम करें।
- यदि मध्यबिंदु का मान कम है, तो निम्न को बढ़ाएँ।
/* [1] ...जारी */
मध्य = (निम्न + (उच्च - निम्न)) / 2;
अगर (आगमन [मध्य] == search_number)
वापस करना मध्य;
अन्यअगर (आगमन [मध्य]> search_number)
उच्च = मध्य - 1;
अन्य
निम्न = मध्य + 1;
उपयोगकर्ता इनपुट के साथ फ़ंक्शन का परीक्षण करें। उपयोग स्कैनफ () कमांड लाइन से इनपुट प्राप्त करने के लिए, जिसमें सरणी आकार, इसकी सामग्री और खोज करने के लिए एक संख्या शामिल है:
int यहाँमुख्य(){
int यहाँ गिरफ्तार [100], मैं, arr_size, search_number;
प्रिंटफ ("तत्वों की संख्या दर्ज करें: ");
स्कैनफ़("%डी", &arr_size);
प्रिंटफ ("कृपया नंबर दर्ज करें: ");के लिए (मैं = 0; मैं < आगमन_आकार; मैं++) {
स्कैनफ़("%डी", &आगमन [मैं]);
}प्रिंटफ ("खोजे जाने वाले नंबर दर्ज करें: ");
स्कैनफ़("%डी", &search_number);i = बाइनरीसर्च (गिरफ्तारी, arr_size, search_number);
अगर (मैं == - 1)
प्रिंटफ ("नंबर मौजूद नहीं है");
अन्य
प्रिंटफ ("संख्या स्थिति %d पर मौजूद है", आई + 1);
वापस करना0;
}
यदि आप संख्या पाते हैं, तो उसकी स्थिति या अनुक्रमणिका प्रदर्शित करें, अन्यथा यह बताने वाला संदेश मौजूद नहीं है कि संख्या मौजूद नहीं है।
C++ का उपयोग करके बाइनरी खोज
आप सी प्रोग्राम को आयात करके सी ++ प्रोग्राम में परिवर्तित कर सकते हैं इनपुट आउटपुट स्ट्रीम और नेमस्पेस एसटीडी का प्रयोग करें पूरे कार्यक्रम में इसे कई बार दोहराने से बचने के लिए।
#शामिल करना <iostream>
का उपयोग करते हुए नाम स्थानकक्षा;उपयोग अदालत निष्कर्षण ऑपरेटर के साथ << के बजाय प्रिंटफ () और सिने सम्मिलन ऑपरेटर के साथ >> के बजाय स्कैनफ () और आपका C++ प्रोग्राम तैयार है।
प्रिंटफ ("तत्वों की संख्या दर्ज करें: ");
अदालत <<"तत्वों की संख्या दर्ज करें: ";
स्कैनफ़("%डी", &arr_size);
सिने >> आगमन_आकार;पायथन का उपयोग करके बाइनरी खोज
जैसा कि पायथन में सरणियों के लिए अंतर्निहित समर्थन नहीं है, सूचियों का उपयोग करें। एक समारोह परिभाषित करें, द्विआधारी खोज(), जो तीन मापदंडों को स्वीकार करता है, सूची, उसका आकार और खोजने के लिए एक संख्या:
डीईएफ़द्विआधारी खोज(आगमन, arr_size, search_number):
कम = 0
उच्च = arr_size - 1
जबकि कम <= उच्च:
मध्य = निम्न + (उच्च-निम्न)//2
अगर आगमन [मध्य] == search_number:
वापस करना मध्य
elif आगमन [मध्य]> search_number:
उच्च = मध्य - 1
अन्य:
निम्न = मध्य + 1
वापस करना-1दो चर प्रारंभ करें, कम और उच्च, सूची के निचले और ऊपरी सीमा के रूप में सेवा करने के लिए। सी कार्यान्वयन के समान, ए का उपयोग करें जबकि लूप जो खोज स्थान को कम करता है। प्रारंभ मध्य सूची के मध्य मूल्य को संग्रहीत करने के लिए। पायथन फ्लोर डिवीजन ऑपरेटर (//) प्रदान करता है जो सबसे बड़ा संभव पूर्णांक प्रदान करता है।
तुलना करें और खोज स्थान को तब तक सीमित करें जब तक कि मध्य मान खोज संख्या के बराबर न हो जाए। यदि खोज संख्या मौजूद नहीं है, तो नियंत्रण वापस आ जाएगा -1.
arr_size = int (इनपुट ("तत्वों की संख्या दर्ज करें: "))
आगमन = []
प्रिंट ("कृपया नंबर दर्ज करें: ", अंत ="")
मैं सीमा में (0,arr_size) के लिए:
आगमन.परिशिष्ट(int यहाँ(इनपुट ()))
search_number = int (इनपुट ("खोजे जाने वाले नंबर दर्ज करें: "))
परिणाम = बाइनरीसर्च (गिरफ्तारी, arr_size, search_number)
यदि परिणाम == -1:
प्रिंट ("नंबर मौजूद नहीं है")
अन्य:
प्रिंट ("संख्या है स्थिति पर मौजूद", (परिणाम + 1))उपयोगकर्ता इनपुट के साथ फ़ंक्शन का परीक्षण करें। उपयोग इनपुट () सूची का आकार, उसकी सामग्री और खोजने के लिए संख्या प्राप्त करने के लिए। उपयोग इंट () पायथन द्वारा स्वीकार किए गए स्ट्रिंग इनपुट को एक पूर्णांक में डिफ़ॉल्ट रूप से टाइपकास्ट करने के लिए। सूची में संख्याएँ जोड़ने के लिए, का उपयोग करें संलग्न () समारोह।
पुकारना द्विआधारी खोज() और तर्क पारित करें। यदि आप संख्या पाते हैं, तो उसकी स्थिति या अनुक्रमणिका प्रदर्शित करें, अन्यथा यह बताने वाला संदेश मौजूद नहीं है कि संख्या मौजूद नहीं है।
बाइनरी सर्च एल्गोरिथम का आउटपुट
निम्नलिखित बाइनरी सर्च एल्गोरिथम का आउटपुट है जब तत्व सरणी में मौजूद होता है:
निम्नलिखित बाइनरी सर्च एल्गोरिथम का आउटपुट है जब तत्व सरणी में मौजूद नहीं है:
मौलिक डेटा संरचनाएं और एल्गोरिदम सीखें
खोज करना आपके द्वारा सीखे जाने वाले पहले एल्गोरिदम में से एक है और अक्सर कोडिंग प्रतियोगिता, प्लेसमेंट और साक्षात्कार में पूछा जाता है। कुछ अन्य एल्गोरिदम जिन्हें आपको सीखना चाहिए वे हैं सॉर्टिंग, हैशिंग, डायनेमिक प्रोग्रामिंग, स्ट्रिंग मैचिंग और प्राइमलिटी टेस्टिंग एल्गोरिदम।
इसके अतिरिक्त, एल्गोरिदम के समय और स्थान की जटिलता को समझना आवश्यक है। वे किसी भी एल्गोरिदम की दक्षता निर्धारित करने में कंप्यूटर विज्ञान में सबसे महत्वपूर्ण अवधारणाओं में से एक हैं। डेटा संरचनाओं और एल्गोरिदम के ज्ञान के साथ, आप सर्वोत्तम प्रोग्राम बनाने के लिए बाध्य हैं।
