रैखिक और द्विआधारी खोज एल्गोरिदम समझाया गया

कुछ डेटा खोजने की क्षमता कंप्यूटर विज्ञान का एक महत्वपूर्ण पहलू है। डेटा सेट में किसी विशेष आइटम को देखने के लिए खोज एल्गोरिदम का उपयोग किया जाता है।

एल्गोरिदम एक खोज क्वेरी के लिए एक बूलियन परिणाम (सत्य या गलत) लौटाता है। पाया मूल्य की सापेक्ष स्थिति देने के लिए उन्हें संशोधित भी किया जा सकता है।

इस आलेख के लिए, एल्गोरिदम यह निर्धारित करने पर ध्यान केंद्रित करेगा कि कोई मान मौजूद है या नहीं।

रैखिक खोज एल्गोरिदम

रैखिक खोज को अनुक्रमिक खोज के रूप में भी जाना जाता है। इस प्रकार की खोज में, सूची में प्रत्येक मान को एक-एक करके क्रमबद्ध तरीके से देखा जाता है, जबकि यह जांचा जाता है कि वांछित मान मौजूद है या नहीं।

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

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

एक उदाहरण के रूप में नीचे दिए गए पायथन कार्यान्वयन को देखें:

def रैखिक खोज (mylist, आइटम):

पाया = झूठा

सूचकांक = 0

जबकि सूचकांक

अगर मेरी सूची [सूचकांक] == आइटम:

पाया = सच

अन्य:

अनुक्रमणिका = अनुक्रमणिका+1

वापसी मिली

एल्गोरिथम विश्लेषण

सबसे अच्छी स्थिति तब होती है जब वांछित वस्तु सूची में सबसे पहले होती है। सबसे खराब स्थिति तब होती है जब वांछित वस्तु सूची में अंतिम (nth आइटम) होती है। इसलिए, रैखिक खोज के लिए समय जटिलता ओ (एन) है।

उपरोक्त एल्गोरिथम में औसत केस परिदृश्य n/2 है।

संबंधित: बिग-ओ नोटेशन क्या है?

संशोधित रैखिक खोज

यह जानना महत्वपूर्ण है कि प्रयुक्त एल्गोरिथम यह मानता है कि उसे वस्तुओं की एक यादृच्छिक सूची प्रदान की गई है। अर्थात्, सूची आइटम किसी विशेष क्रम में नहीं हैं।

मान लीजिए कि आइटम एक विशेष क्रम में थे, जैसे कि सबसे छोटे से सबसे बड़े तक। संगणना में कुछ लाभ प्राप्त करना संभव होगा।

दी गई सूची में 19 खोजने का एक उदाहरण लें: [2, 5, 6, 11, 15, 18, 23, 27, 34]। 23 पर पहुंचने के बाद, यह स्पष्ट हो जाएगा कि जिस वस्तु की तलाश की जा रही है वह सूची में मौजूद नहीं है। इसलिए, सूची के बाकी आइटमों की खोज जारी रखना अब महत्वपूर्ण नहीं होगा।

बाइनरी सर्च एल्गोरिदम

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

एल्गोरिथम एक ऑर्डर की गई सूची के मध्य मान को लेकर शुरू होता है और जांचता है कि यह वांछित मूल्य है या नहीं। यदि ऐसा नहीं है, तो मान की जाँच की जाती है कि क्या यह वांछित मान से कम या अधिक है।

यदि यह कम है, तो सूची के निचले आधे हिस्से की जांच करने की कोई आवश्यकता नहीं है। अन्यथा, यदि यह बड़ा है, तो यह सूची के ऊपरी भाग में चला जाता है।

संबंधित: रिकर्सन क्या है और आप इसका उपयोग कैसे करते हैं?

चाहे जो भी सबलिस्ट (बाएं या दाएं) चुना जाए, मध्य मान फिर से निर्धारित किया जाएगा। यदि यह आवश्यक मान है तो मान को फिर से चेक किया जाता है। यदि ऐसा नहीं है, तो यह जांचा जाता है कि यह अनुरोधित मान से कम है या अधिक।

यह प्रक्रिया तब तक दोहराई जाती है जब तक कोई मान नहीं मिल जाता है।

नीचे दिया गया पायथन कार्यान्वयन बाइनरी सर्च एल्गोरिथम के लिए है।

def बाइनरीसर्च (mylist, आइटम):

कम = 0

उच्च = लेन (माईलिस्ट) - 1

पाया = झूठा

जबकि कम <= उच्च और नहीं मिला:

मध्य = (निम्न + उच्च) // 2

अगर मेरी सूची [मध्य] == आइटम:

पाया = सच

एलिफ आइटम

उच्च = मध्य - 1

अन्य:

कम = मध्य + 1

वापसी मिली

एल्गोरिथम विश्लेषण

सबसे अच्छी स्थिति तब होती है जब वांछित वस्तु मध्य वस्तु पाई जाती है। हालांकि सबसे खराब स्थिति इतनी सीधी नहीं है। नीचे दिए गए विश्लेषण का पालन करें:

पहली तुलना के बाद, n/2 आइटम बचे रहेंगे। सेकंड के बाद, n/4 आइटम बचे रहेंगे। तीसरे के बाद, n/8।

ध्यान दें कि वस्तुओं की संख्या तब तक आधी होती रहती है जब तक कि वे n/2i तक नहीं पहुँच जाती जहाँ i तुलनाओं की संख्या है। सभी बंटवारे के बाद, हम केवल 1 आइटम के साथ समाप्त होते हैं।

इसका अर्थ है:

एन/2i=1

इसलिए, द्विआधारी खोज ओ (लॉग एन) है।

छँटाई के लिए आगे बढ़ना

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

उत्तर सरल है: इसे क्रमबद्ध करें। कंप्यूटर विज्ञान में कई छँटाई तकनीकें हैं जिन पर अच्छी तरह से शोध किया गया है। इनमें से एक तकनीक जिसे आप पढ़ना शुरू कर सकते हैं, वह है सिलेक्शन सॉर्ट एल्गोरिथम, जबकि हमारे पास अन्य क्षेत्रों से संबंधित कई गाइड भी हैं।

चयन क्रम का उपयोग कैसे करें

शुरुआती लोगों के लिए चयन प्रकार को समझना थोड़ा मुश्किल है, लेकिन एक बार जब आप चीजों को स्विंग कर लेते हैं तो यह बहुत चुनौतीपूर्ण नहीं होता है।

आगे पढ़िए

लेखक के बारे में