रेखीय खोज

रेखीय खोज

Class	Search algorithm
Worst-case performance	O(n)
Best-case performance	O(1)
Average performance	O(n)
Worst-case space complexity	O(1) iterative

कंप्यूटर विज्ञान में, रैखिक खोज या अनुक्रमिक खोज सूची (कंप्यूटिंग) के अंदर तत्व खोजने की विधि होती है। यह सूची के प्रत्येक तत्व की क्रमिक रूप से जांच करता है जब तक कि कोई मिलान नहीं मिल जाता या पूर्ण सूची खोज नहीं ली जाती है ।

इस प्रकार से एक रेखीय खोज सबसे व्यर्थ समय जटिलता या रैखिक समय में चलती रहती है और अधिकतम n तुलना करती है जहाँ n सूची की लंबाई है ।यदि प्रत्येक तत्व को खोजे जाने की समान संभावना है, तो रैखिक n+1/2 खोज की औसत स्तिथि होती है तुलना, किन्तु यदि प्रत्येक तत्व के लिए खोज संभावनाएं भिन्न होती हैं तो औसत स्तिथि प्रभावित हो सकती है। और रैखिक खोज संभवतः ही कभी व्यावहारिक होती है क्योंकि अन्य खोज एल्गोरिदम और योजनाएं, जैसे कि बाइनरी खोज एल्गोरिदम और हैश तालिका , छोटी सूचियों को छोड़कर सभी के लिए अधिक तीव्र खोज की अनुमति देती हैं।

एल्गोरिदम

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

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

मूल्यों या रिकॉर्ड L₀ .... L_n−1, और लक्ष्य मान T के साथ n तत्वों की एक सूची L को देखते हुए, निम्नलिखित सबरूटीन L में लक्ष्य T के सूचकांक को खोजने के लिए रैखिक खोज का उपयोग करता है।

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

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

इस प्रकार से उपरोक्त मूल एल्गोरिदम प्रति पुनरावृत्ति दो तुलना करता है: एक यह जांचने के लिए कि क्या Li T के समान है, और दूसरा यह जांचने के लिए कि क्या मैं अभी भी सूची के वैध सूचकांक i को इंगित करता हूं। सूची में एक अतिरिक्त रिकॉर्ड L_n (एक प्रहरी मान) जोड़कर जो लक्ष्य के समान है, खोज के अंत तक दूसरी तुलना को समाप्त किया जा सकता है, जिससे एल्गोरिदम तीव्र हो जाता है। यदि लक्ष्य सूची में सम्मिलित नहीं होते है तो खोज प्रहरी तक पहुंच जाती है।

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

एक आदेशित तालिका में

अतः यदि सूची इस प्रकार क्रमबद्ध होती है की L₀ ≤ L₁ ... ≤ L_n−1, खोज बार समाप्त करके लक्ष्य की अनुपस्थिति को अधिक तीव्र से स्थापित कर सकती है जब L_i लक्ष्य से अधिक है। इस भिन्नता के लिए ऐसे प्रहरी की आवश्यकता होती है जो लक्ष्य से अधिक उच्च हो।

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

विश्लेषण

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

यदि मांगा जा रहा मूल्य सूची में k बार आता है, और सूची के सभी क्रम समान रूप से संभावित हैं, तो तुलनाओं की अपेक्षित संख्या है

${\begin{cases}n&{\mbox{if }}k=0\\[5pt]\displaystyle {\frac {n+1}{k+1}}&{\mbox{if }}1\leq k\leq n.\end{cases}}$

उदाहरण के लिए, यदि मांगा जा रहा मूल्य सूची में बार आता है, और सूची के सभी क्रम समान रूप से संभावित हैं, तो तुलनाओं की अपेक्षित संख्या है ${\frac {n+1}{2}}$ है. चूँकि , यदि यह ज्ञात है कि यह बार होता है, तो अधिकतम n - 1 तुलनाओं की आवश्यकता होती है, और तुलनाओं की अपेक्षित संख्या है

$\displaystyle {\frac {(n+2)(n-1)}{2n}}$

(उदाहरण के लिए, n = 2 के लिए यह 1 है, जो एकल यदि-तब-अन्यथा निर्माण के अनुरूप है)।

किसी भी प्रकार से, असम्बद्ध रूप से सबसे व्यर्थ स्थिति की निवेश और रैखिक खोज की अपेक्षित निवेश दोनों O(n) हैं।

गैर-समान संभावनाएँ

चूँकि यदि वांछित मान सूची के अंत की तुलना में प्रारंभ के निकट होने की अधिक संभावना है, तो रैखिक खोज का प्रदर्शन श्रेष्ठ हो जाता है। इसलिए, यदि कुछ मूल्यों को दूसरों की तुलना में खोजे जाने की अधिक संभावना होती है, तो उन्हें सूची की प्रारंभ में रखना वांछनीय है।

विशेष रूप से, जब सूची आइटम को घटती संभावना के क्रम में व्यवस्थित किया जाता है, और ये संभावनाएं ज्यामितीय रूप से वितरित किया जाता हैं, तो रैखिक खोज की निवेश केवल O(1) होती है।

आवेदन

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

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

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

यह भी देखें

• टर्नरी खोज
• हैश तालिका
• रेखीय खोज समस्या

संदर्भ

कार्य

• Knuth, Donald (1998). Sorting and Searching. The Art of Computer Programming. Vol. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional. ISBN 0-201-89685-0

श्रेणी:खोज एल्गोरिदम