रेखीय खोज

रेखीय खोज

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 पर जाएँ। अन्यथा, खोज असफल रूप से समाप्त हो जाती है।

प्रहरी के साथ

इस प्रकार से उपरोक्त मूल एल्गोरिदम प्रति पुनरावृत्ति दो तुलना करता है | यह जांचने के लिए कि क्या L_i 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

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