सदस्य:AayushiRK/sandbox/1

मुक्त ज्ञानकोश विकिपीडिया से

रैखिक खोज (लिनियर सर्च)

कंप्यूटर विज्ञान में, रैखिक खोज या अनुक्रमिक खोज , एक विधि है जो एक सूची के भीतर एक लक्ष्य मूल्य को ढूँढने के लिए प्रयोग कि जाती है । यह क्रमिक रूप से लक्ष्य मान के लिए सूची के प्रत्येक तत्व को तब तक जांचता है जब तक कोई मिलान नहीं मिलता है या जब तक सभी तत्वों की खोज नहीं हुई हो।

'रैखिक खोज

रैखिक खोज शायद ही व्यावहारिक होती है क्योंकि अन्य खोज एल्गोरिदम और योजनाएं, जैसे कि द्विआधारी खोज एल्गोरिथ्म और हैश तालिकाओं, सभी के लिए मात्र छोटी सूची के लिए काफी तेज़ खोज की अनुमति देती हैं।

एल्गोरिथम

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

मूल एल्गोरिथम

एक सूची L, n तत्वों का मूल्यों या अभिलेखों के साथ L0 .... Ln−1 और लक्ष्य मूल्य T , निम्न उपकार्यक्रम L में लक्ष्य T के सूचक को खोजने के लिए रैखिक खोज का उपयोग किया जाता है ।

  1. i को 0 पर सेट करें ।
  2. यदि Li = T, खोज सफलतापूर्वक समाप्त हो जत है और फिर i को वापस कर्ते है ।
  3. अब i को 1 से बढ़ाएं
  4. अगर i < n , चरण 2 पर जाएं ; अन्यथा, खोज असफल रूप से समाप्त हो जाता है ।


एक प्रहरी के साथ

उपरोक्त मूल एल्गोरिथ्म प्रति पुनरावृत्ति में दो तुलना ही करता है : एक यह जांचने के लिए कि क्या Li t के बराबर है , और दूसरा यह जांचने के लिए कि क्या i अभी भी सूची के एक मान्य सूचक को इंगित करता है

प्रयोग

रैखिक खोज आमतौर पर लागू करने के लिए बहुत सरल होता है , और व्यावहारिक होता है जब सूची में केवल कुछ तत्व हो , या जब एक अव्यवस्थित ( या अनोर्ड ) सूची में कोई सिंगल खोज ( या एकल खोज ) करते हैं ।

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

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

रैखिक खोज समस्या

कम्प्यूटेशनल जटिलता सिद्धांत में, रैखिक खोज समस्या रिचर्ड ई। बेलमैन द्वारा पेश की जाने वाली एक इष्टतम खोज समस्या है। (स्वतंत्र रूप से एनाटोल बेक द्वारा विचार किया गया)।


[1] [2]

  1. https://en.wikipedia.org/wiki/Linear_search
  2. https://www.geeksforgeeks.org/linear-search/