विषय

• तुलना चार्ट
• रैखिक खोज की परिभाषा
• बाइनरी सर्च की परिभाषा
• निष्कर्ष

रैखिक खोज और द्विआधारी खोज दो तरीके हैं जिनके लिए सरणियों में उपयोग किया जाता है खोज कर अवयव। खोज किसी भी क्रम में या यादृच्छिक रूप से संग्रहीत तत्वों की सूची के भीतर एक तत्व खोजने की एक प्रक्रिया है।

रैखिक खोज और बाइनरी खोज के बीच प्रमुख अंतर यह है कि द्विआधारी खोज में तत्वों की क्रमबद्ध सूची से किसी तत्व को खोजने के लिए कम समय लगता है। इसलिए यह अनुमान लगाया जाता है कि द्विआधारी खोज विधि की दक्षता रैखिक खोज से अधिक है।

दोनों के बीच एक और अंतर यह है कि द्विआधारी खोज के लिए एक शर्त है, अर्थात, तत्व होने चाहिए क्रमबद्ध जबकि रैखिक खोज में ऐसी कोई शर्त नहीं है। यद्यपि दोनों खोज विधियां विभिन्न तकनीकों का उपयोग करती हैं जो नीचे चर्चा की गई हैं।

1. तुलना चार्ट
2. परिभाषा
3. मुख्य अंतर
4. निष्कर्ष

तुलना चार्ट

तुलना के लिए आधार	रैखिक खोज	द्विआधारी खोज
समय जटिलता	पर)	हे (लॉग 2 एन)
सबसे अच्छा मामला समय	पहला तत्व हे (1)	केंद्र तत्व हे (1)
किसी सरणी के लिए पूर्वापेक्षा	जरूरत नहीं	एरियर को क्रमबद्ध क्रम में होना चाहिए
तत्वों की एन संख्या के लिए सबसे खराब मामला	एन तुलना की आवश्यकता है	केवल लॉग के बाद निष्कर्ष निकाल सकते हैं2एन तुलना
पर लागू किया जा सकता है	एरे और लिंक्ड सूची	लिंक की गई सूची पर सीधे लागू नहीं किया जा सकता है
ऑपरेशन डालें	आसानी से सूची के अंत में डाला गया	क्रमबद्ध सूची को बनाए रखने के लिए इसके उचित स्थान पर प्रसंस्करण की आवश्यकता होती है।
एल्गोरिथम प्रकार	स्वभाव में निष्क्रिय	प्रकृति में फूट डालो और जीतो
उपयोगिता	उपयोग करने के लिए आसान और किसी भी आदेशित तत्वों की आवश्यकता नहीं है।	किसी भी तरह मुश्किल एल्गोरिथ्म और तत्वों को व्यवस्थित किया जाना चाहिए।
कोड की पंक्तियाँ	कम	अधिक

रैखिक खोज की परिभाषा

एक रेखीय खोज में, सरणी के प्रत्येक तत्व को तार्किक क्रम में एक-एक करके पुनर्प्राप्त किया जाता है और यह जांचा जाता है कि यह वांछित तत्व है या नहीं। सभी तत्वों तक पहुंचने पर एक खोज असफल हो जाएगी, और वांछित तत्व नहीं मिला है। सबसे खराब स्थिति में, एक औसत मामले की संख्या हमें सरणी के आकार (एन / 2) के आधे हिस्से को स्कैन करने की हो सकती है।

इसलिए रैखिक खोज को उस तकनीक के रूप में परिभाषित किया जा सकता है जो दी गई वस्तु का पता लगाने के लिए क्रमिक रूप से सरणी का पता लगाती है। नीचे दिया गया कार्यक्रम खोज का उपयोग करके सरणी के एक तत्व की खोज को दिखाता है।

दक्षता रैखिक खोज का

खोज तालिका में रिकॉर्ड की खोज में किए गए समय की खपत या तुलना की संख्या तकनीक की दक्षता निर्धारित करती है। यदि वांछित तालिका खोज तालिका की पहली स्थिति में मौजूद है, तो केवल एक तुलना की जाती है। जब वांछित रिकॉर्ड अंतिम होता है, तो एन तुलना करना पड़ता है। यदि रिकॉर्ड खोज तालिका में कहीं प्रस्तुत करना है, तो औसतन, तुलना की संख्या (n + 1/2) होगी। इस तकनीक की सबसे खराब स्थिति O (n) है जो निष्पादन के क्रम के लिए है।

C कार्यक्रम रैखिक खोज तकनीक के साथ एक तत्व की खोज करने के लिए।

#शामिल #शामिल शून्य मुख्य () {int a, n, i, item, loc = -1; clrscr (); च ("तत्व की संख्या को निर्धारित करें:"); स्कैनफ़ ("% d", & n); f ("नंबर दर्ज करें: n"); for (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f ("खोजे जाने वाली संख्या के लिए n": "); स्कैनफ़ ("% d", और आइटम); for (i = 0; i <= n-1; i ++) {if (आइटम == ए) {loc = i; टूटना; }} अगर (लोकेशन> = 0) {f (" n% d पोजिशन% d में पाया जाता है:", आइटम, लोकेशन + 1); } और {f (" n आइटम मौजूद नहीं है"); } getch (); }

बाइनरी सर्च की परिभाषा

बाइनरी खोज एक अत्यंत कुशल एल्गोरिथ्म है। यह खोज तकनीक दी गई वस्तु को न्यूनतम संभव तुलना में खोजने में कम समय लगाती है। बाइनरी खोज करने के लिए, पहले, हमें एरे तत्वों को सॉर्ट करना होगा।

इस तकनीक के पीछे तर्क नीचे दिया गया है:

• सबसे पहले, सरणी के मध्य तत्व को ढूंढें।
• सरणी के मध्य तत्व को खोजे जाने वाले तत्व की तुलना में है।

तीन मामले सामने आ सकते हैं:

1. यदि तत्व आवश्यक तत्व है, तो खोज सफल है।
2. जब तत्व वांछित आइटम से कम है, तो केवल सरणी के पहले छमाही को खोजें।
3. यदि यह वांछित तत्व से अधिक है, तो सरणी के दूसरे छमाही में खोजें।

जब तक कोई तत्व नहीं मिलता है या खोज क्षेत्र में निकास नहीं होता है तब तक वही चरण दोहराएं। इस एल्गोरिथ्म में, हर बार खोज क्षेत्र कम हो रहा है। इसलिए तुलना की संख्या सबसे अधिक लॉग (एन + 1) पर है। नतीजतन, यह रैखिक खोज की तुलना में एक कुशल एल्गोरिदम है, लेकिन बाइनरी खोज करने से पहले सरणी को क्रमबद्ध करना पड़ता है।

C कार्यक्रम द्विआधारी खोज तकनीक के साथ एक तत्व खोजने के लिए।

#शामिल शून्य मुख्य () {इंट i, भीख, अंत, मध्य, एन, खोज, सरणी; एफ ("तत्व की संख्या दर्ज करें n"); scanf ( "% d", और एन); f ("% d नंबर n दर्ज करें", n); for (i = 0; i <n; i ++) स्कैनफ ("% d", और सरणी); f ("एन्टर की जाने वाली संख्या दर्ज करें"); स्कैनफ़ ("% d", और खोज); भीख = 0; अंत = एन - 1; मध्य = (भीख + अंत) / 2; जबकि (भीख माँगना = समाप्त करना) {अगर (सरणी <खोज) भीख माँगना = मध्य + १; अगर (सरणी == खोज) {f ("खोज सफल है। n% d को स्थान% d पर मिला। n", खोज, मध्य + 1); टूटना; } और अंत = मध्य - 1; मध्य = (भीख + अंत) / 2; } अगर (भीख) अंत (च) "खोज असफल है!% d सूची में मौजूद नहीं है। n", खोज); getch (); }

1. रैखिक खोज प्रकृति में पुनरावृत्त है और अनुक्रमिक दृष्टिकोण का उपयोग करता है। दूसरी ओर, द्विआधारी खोज लागू करते हैं और दृष्टिकोण को जीतते हैं।
2. रैखिक खोज की समय जटिलता O (N) है जबकि बाइनरी खोज में O (लॉग) है₂एन)।
3. रैखिक खोज में सबसे अच्छा मामला समय पहले तत्व के लिए है, अर्थात्, ओ (1)। जैसा कि द्विआधारी खोज में है, यह मध्य तत्व के लिए है, अर्थात, ओ (1)।
4. रैखिक खोज में, किसी तत्व को खोजने के लिए सबसे खराब स्थिति तुलना की संख्या है। इसके विपरीत, यह लॉग है₂बाइनरी खोज के लिए तुलना की एन संख्या।
5. रैखिक खोज को एक सरणी के साथ-साथ लिंक्ड सूची में भी लागू किया जा सकता है जबकि बाइनरी खोज को सीधे लिंक की गई सूची पर लागू नहीं किया जा सकता है।
6. जैसा कि हम जानते हैं कि द्विआधारी खोज को क्रमबद्ध सरणी की आवश्यकता होती है, इसका कारण यह है कि क्रमबद्ध सूची को बनाए रखने के लिए इसके उचित स्थान पर प्रसंस्करण की आवश्यकता होती है। इसके विपरीत रैखिक खोज में हल किए गए तत्वों की आवश्यकता नहीं होती है, इसलिए सूची के अंत में तत्वों को आसानी से डाला जाता है।
7. रैखिक खोज का उपयोग करना आसान है, और किसी भी आदेशित तत्वों की आवश्यकता नहीं है। दूसरी ओर, द्विआधारी खोज एल्गोरिथ्म हालांकि मुश्किल है, और तत्वों को आवश्यक रूप से व्यवस्थित किया जाता है।

निष्कर्ष

रैखिक और द्विआधारी खोज एल्गोरिदम दोनों आवेदन के आधार पर उपयोगी हो सकते हैं। जब कोई सरणी डेटा संरचना होती है और तत्वों को क्रमबद्ध क्रम में व्यवस्थित किया जाता है, तो बाइनरी खोज को प्राथमिकता दी जाती है शीघ्रखोज कर। यदि लिंक की गई सूची डेटा संरचना है, भले ही तत्वों की व्यवस्था कैसे की जाए, तो द्विआधारी खोज एल्गोरिथ्म के प्रत्यक्ष कार्यान्वयन की अनुपलब्धता के कारण रैखिक खोज को अपनाया जाता है।

विशिष्ट बाइनरी सर्च एल्गोरिदम को लिंक्ड सूची में नियोजित नहीं किया जा सकता है क्योंकि लिंक्ड सूची प्रकृति में गतिशील है और यह ज्ञात नहीं है कि मध्य तत्व वास्तव में कहाँ सौंपा गया है। इसलिए, द्विआधारी खोज एल्गोरिदम की भिन्नता को डिजाइन करने की आवश्यकता है जो लिंक की गई सूची पर भी काम कर सकती है क्योंकि बाइनरी खोज रैखिक खोज की तुलना में निष्पादन में तेज है।