रैखिक खोज और बाइनरी खोज के बीच अंतर

2019

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

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

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

तुलना चार्ट

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

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

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

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

रैखिक खोज की क्षमता

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

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

 #include #include void main () {int a [100], n, i, item, loc = -1; clrscr (); प्रिंटफ ("तत्व की संख्या को निर्धारित करें:"); स्कैनफ़ ("% d", & n); प्रिंटफ ("नंबर दर्ज करें: \ n"); for (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } प्रिंटफ ("खोजे जाने वाले नंबर के लिए \ n": "); स्कैनफ़ ("% d", और आइटम); के लिए (i = 0; i = 0) {प्रिंटफ ("\ n% d स्थिति% d में पाया जाता है:", आइटम, लोक + 1); } और {प्रिंटफ ("\ n आइटम मौजूद नहीं है"); } getch (); }

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

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

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

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

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

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

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

सी प्रोग्राम बाइनरी सर्च तकनीक के साथ एक तत्व खोजने के लिए।

 #include void main () {int i, beg, end, Middle, n, search, array [100]; प्रिंटफ ("तत्व की संख्या दर्ज करें \ n"); scanf ( "% d", और एन); printf ("% d संख्या \ n दर्ज करें", n); के लिए (i = 0; मैं <n; i ++) स्कैनफ ("% d", और सरणी [i]); प्रिंटफ ("एन्टर की जाने वाली संख्या दर्ज करें"); स्कैनफ़ ("% d", और खोज); भीख = 0; अंत = एन - 1; मध्य = (भीख + अंत) / 2; जबकि (भीख मांगना = समाप्त करना) {अगर (एरे [मध्य] अंत) प्रिंटफ ("खोज असफल है!% d सूची में मौजूद नहीं है। \ n", खोज) getch (); }

रैखिक खोज और बाइनरी खोज के बीच महत्वपूर्ण अंतर

निष्कर्ष

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

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