रेखीय खोज: Difference between revisions

रेखीय खोज
Class	Search algorithm
Worst-case performance	O(n)
Best-case performance	O(1)
Average performance	O(n)
Worst-case space complexity	O(1) iterative

Revision as of 13:51, 5 July 2023

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

एक रेखीय खोज सबसे खराब समय जटिलता#रैखिक समय में चलती है और अधिकतम बनाती है $n$ तुलना, कहाँ $n$ सूची की लंबाई है. यदि प्रत्येक तत्व को खोजे जाने की समान संभावना है, तो रैखिक खोज का औसत मामला होता है $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}n+1/2$ तुलना, लेकिन यदि प्रत्येक तत्व के लिए खोज संभावनाएं भिन्न होती हैं तो औसत मामला प्रभावित हो सकता है। रैखिक खोज शायद ही कभी व्यावहारिक होती है क्योंकि अन्य खोज एल्गोरिदम और योजनाएं, जैसे कि बाइनरी खोज एल्गोरिदम और हैश तालिका , छोटी सूचियों को छोड़कर सभी के लिए काफी तेज़ खोज की अनुमति देती हैं।^[2]

एल्गोरिदम

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

बुनियादी एल्गोरिदम

एक सूची दी गई $L$ का $n$ मान या रिकॉर्ड वाले तत्व (कंप्यूटर विज्ञान) $L 0 .... L n -1$ , और लक्ष्य मान $T$ , निम्नलिखित सबरूटीन लक्ष्य के सूचकांक को खोजने के लिए रैखिक खोज का उपयोग करता है $T$ में $L$ .^[3]

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

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

उपरोक्त मूल एल्गोरिदम प्रति पुनरावृत्ति दो तुलना करता है: यह जांचने के लिए कि क्या $L i$ टी के बराबर है, और दूसरा यह जांचने के लिए है $i$ अभी भी सूची के वैध सूचकांक की ओर इशारा करता है। अतिरिक्त रिकॉर्ड जोड़कर $L n$ सूची में (एक प्रहरी मान) जो लक्ष्य के बराबर है, दूसरी तुलना को खोज के अंत तक समाप्त किया जा सकता है, जिससे एल्गोरिदम तेज़ हो जाता है। यदि लक्ष्य सूची में शामिल नहीं है तो खोज प्रहरी तक पहुंच जाएगी।^[4]

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

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

यदि सूची इस प्रकार क्रमबद्ध है $L 0 \leq L 1 ... \leq L n -1$ , खोज बार समाप्त करके लक्ष्य की अनुपस्थिति को अधिक तेज़ी से स्थापित कर सकती है $L i$ लक्ष्य से अधिक है। इस भिन्नता के लिए ऐसे प्रहरी की आवश्यकता होती है जो लक्ष्य से अधिक बड़ा हो।^[5]

तय करना $i$ से 0.
अगर $L i \geq T$ , चरण 4 पर जाएँ।
बढ़ोतरी $i$ 1 से और चरण 2 पर जाएँ।
अगर $L i = T$ , खोज सफलतापूर्वक समाप्त हो जाती है; वापस करना $i$ . अन्यथा, खोज असफल रूप से समाप्त हो जाती है।

विश्लेषण

एन आइटम वाली सूची के लिए, सबसे अच्छा मामला तब होता है जब मान सूची के पहले तत्व के बराबर होता है, उस स्थिति में केवल तुलना की आवश्यकता होती है। सबसे खराब स्थिति तब होती है जब मान सूची में नहीं होता है (या सूची के अंत में केवल बार होता है), उस स्थिति में 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 है, जो एकल if-then-else निर्माण के अनुरूप है)।

किसी भी तरह से, स्पर्शोन्मुख जटिलता सबसे खराब स्थिति की लागत और रैखिक खोज की अपेक्षित लागत दोनों बड़े ओ अंकन (एन) हैं।

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

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

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

आवेदन

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

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

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

यह भी देखें

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

संदर्भ

उद्धरण

↑ ^1.0 ^1.1 Knuth 1998, §6.1 ("Sequential search").
↑ Knuth 1998, §6.2 ("Searching by Comparison Of Keys").
↑ Knuth 1998, §6.1 ("Sequential search"), subsection "Algorithm B".
↑ Knuth 1998, §6.1 ("Sequential search"), subsection "Algorithm Q".
↑ Knuth 1998, §6.1 ("Sequential search"), subsection "Algorithm T".
↑ Knuth, Donald (1997). "Section 6.1: Sequential Searching". Sorting and Searching. The Art of Computer Programming. Vol. 3 (3rd ed.). Addison-Wesley. pp. 396–408. ISBN 0-201-89685-0.
↑ Horvath, Adam. ".NET और मोनो प्लेटफ़ॉर्म पर बाइनरी खोज और रैखिक खोज प्रदर्शन". Retrieved 19 April 2013.

कार्य

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

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

[FOOTNOTEKnuth1998§6.1_("Sequential_search")-1] 1.0 ^1.1 Knuth 1998, §6.1 ("Sequential search").

[FOOTNOTEKnuth1998§6.2_("Searching_by_Comparison_Of_Keys")-2] Knuth 1998, §6.2 ("Searching by Comparison Of Keys").

[FOOTNOTEKnuth1998§6.1_("Sequential_search"),_subsection_"Algorithm_B"-3] Knuth 1998, §6.1 ("Sequential search"), subsection "Algorithm B".

[FOOTNOTEKnuth1998§6.1_("Sequential_search"),_subsection_"Algorithm_Q"-4] Knuth 1998, §6.1 ("Sequential search"), subsection "Algorithm Q".

[FOOTNOTEKnuth1998§6.1_("Sequential_search"),_subsection_"Algorithm_T"-5] Knuth 1998, §6.1 ("Sequential search"), subsection "Algorithm T".

[knuth-6] Knuth, Donald (1997). "Section 6.1: Sequential Searching". Sorting and Searching. The Art of Computer Programming. Vol. 3 (3rd ed.). Addison-Wesley. pp. 396–408. ISBN 0-201-89685-0.

[7] Horvath, Adam. ".NET और मोनो प्लेटफ़ॉर्म पर बाइनरी खोज और रैखिक खोज प्रदर्शन". Retrieved 19 April 2013.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
-{{short description|Sequentially looking in an array}}
+{{short description|Sequentially looking in an array}}{{Infobox algorithm
-{{Multiple issues|
-{{refimprove|date=November 2010}}
-{{one source|date=November 2010}}
-}}
-{{Infobox algorithm
 |name={{PAGENAMEBASE}}|class=[[Search algorithm]]
 |time=[[big O notation#Orders of common functions|''O''(''n'')]]
@@ Line 15: / Line 9: @@
 }}
-[[कंप्यूटर विज्ञान]] में, एक रैखिक खोज या अनुक्रमिक खोज एक [[सूची (कंप्यूटिंग)]] के भीतर एक तत्व खोजने की एक विधि है। यह सूची के प्रत्येक तत्व की क्रमिक रूप से जांच करता है जब तक कि कोई मिलान नहीं मिल जाता या पूरी सूची खोज नहीं ली जाती।{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search")}}
+[[कंप्यूटर विज्ञान]] में, रैखिक खोज या अनुक्रमिक खोज [[सूची (कंप्यूटिंग)]] के भीतर तत्व खोजने की विधि है। यह सूची के प्रत्येक तत्व की क्रमिक रूप से जांच करता है जब तक कि कोई मिलान नहीं मिल जाता या पूरी सूची खोज नहीं ली जाती।{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search")}}
-एक रेखीय खोज सबसे खराब समय जटिलता#रैखिक समय में चलती है और अधिकतम बनाती है {{math|''n''}} तुलना, कहाँ {{math|''n''}} सूची की लंबाई है. यदि प्रत्येक तत्व को खोजे जाने की समान संभावना है, तो रैखिक खोज का औसत मामला होता है {{math|{{Sfrac|''n+1''|2}}}} तुलना, लेकिन यदि प्रत्येक तत्व के लिए खोज संभावनाएं भिन्न होती हैं तो औसत मामला प्रभावित हो सकता है। रैखिक खोज शायद ही कभी व्यावहारिक होती है क्योंकि अन्य खोज एल्गोरिदम और योजनाएं, जैसे कि [[बाइनरी खोज एल्गोरिदम]] और [[ हैश तालिका ]], छोटी सूचियों को छोड़कर सभी के लिए काफी तेज़ खोज की अनुमति देती हैं।{{Sfn|Knuth|1998|loc=§6.2 ("Searching by Comparison Of Keys")}}
+एक रेखीय खोज सबसे खराब समय जटिलता#रैखिक समय में चलती है और अधिकतम बनाती है {{math|''n''}} तुलना, कहाँ {{math|''n''}} सूची की लंबाई है. यदि प्रत्येक तत्व को खोजे जाने की समान संभावना है, तो रैखिक खोज का औसत मामला होता है {{math|{{Sfrac|''n+1''|2}}}} तुलना, लेकिन यदि प्रत्येक तत्व के लिए खोज संभावनाएं भिन्न होती हैं तो औसत मामला प्रभावित हो सकता है। रैखिक खोज शायद ही कभी व्यावहारिक होती है क्योंकि अन्य खोज एल्गोरिदम और योजनाएं, जैसे कि [[बाइनरी खोज एल्गोरिदम]] और [[ हैश तालिका |हैश तालिका]] , छोटी सूचियों को छोड़कर सभी के लिए काफी तेज़ खोज की अनुमति देती हैं।{{Sfn|Knuth|1998|loc=§6.2 ("Searching by Comparison Of Keys")}}
 ==एल्गोरिदम==
@@ Line 31: / Line 25: @@
 ===एक प्रहरी के साथ===
-उपरोक्त मूल एल्गोरिदम प्रति पुनरावृत्ति दो तुलना करता है: एक यह जांचने के लिए कि क्या {{math|''L''<sub>''i''</sub>}} टी के बराबर है, और दूसरा यह जांचने के लिए है {{math|''i''}} अभी भी सूची के एक वैध सूचकांक की ओर इशारा करता है। एक अतिरिक्त रिकॉर्ड जोड़कर {{math|''L''<sub>''n''</sub>}} सूची में (एक प्रहरी मान) जो लक्ष्य के बराबर है, दूसरी तुलना को खोज के अंत तक समाप्त किया जा सकता है, जिससे एल्गोरिदम तेज़ हो जाता है। यदि लक्ष्य सूची में शामिल नहीं है तो खोज प्रहरी तक पहुंच जाएगी।{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search"), subsection "Algorithm Q"}}
+उपरोक्त मूल एल्गोरिदम प्रति पुनरावृत्ति दो तुलना करता है: यह जांचने के लिए कि क्या {{math|''L''<sub>''i''</sub>}} टी के बराबर है, और दूसरा यह जांचने के लिए है {{math|''i''}} अभी भी सूची के वैध सूचकांक की ओर इशारा करता है। अतिरिक्त रिकॉर्ड जोड़कर {{math|''L''<sub>''n''</sub>}} सूची में (एक प्रहरी मान) जो लक्ष्य के बराबर है, दूसरी तुलना को खोज के अंत तक समाप्त किया जा सकता है, जिससे एल्गोरिदम तेज़ हो जाता है। यदि लक्ष्य सूची में शामिल नहीं है तो खोज प्रहरी तक पहुंच जाएगी।{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search"), subsection "Algorithm Q"}}
 # तय करना {{math|''i''}} से 0.
@@ Line 39: / Line 33: @@
 ===एक आदेशित तालिका में===
-यदि सूची इस प्रकार क्रमबद्ध है {{math|''L''<sub>0</sub> &le; ''L''<sub>1</sub> ... &le; ''L''<sub>''n''−1</sub>}}, खोज एक बार समाप्त करके लक्ष्य की अनुपस्थिति को अधिक तेज़ी से स्थापित कर सकती है {{math|''L''<sub>''i''</sub>}} लक्ष्य से अधिक है। इस भिन्नता के लिए एक ऐसे प्रहरी की आवश्यकता होती है जो लक्ष्य से अधिक बड़ा हो।{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search"), subsection "Algorithm T"}}
+यदि सूची इस प्रकार क्रमबद्ध है {{math|''L''<sub>0</sub> &le; ''L''<sub>1</sub> ... &le; ''L''<sub>''n''−1</sub>}}, खोज बार समाप्त करके लक्ष्य की अनुपस्थिति को अधिक तेज़ी से स्थापित कर सकती है {{math|''L''<sub>''i''</sub>}} लक्ष्य से अधिक है। इस भिन्नता के लिए ऐसे प्रहरी की आवश्यकता होती है जो लक्ष्य से अधिक बड़ा हो।{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search"), subsection "Algorithm T"}}
 # तय करना {{math|''i''}} से 0.
@@ Line 47: / Line 41: @@
 ==विश्लेषण==
-एन आइटम वाली सूची के लिए, सबसे अच्छा मामला तब होता है जब मान सूची के पहले तत्व के बराबर होता है, उस स्थिति में केवल एक तुलना की आवश्यकता होती है। सबसे खराब स्थिति तब होती है जब मान सूची में नहीं होता है (या सूची के अंत में केवल एक बार होता है), उस स्थिति में n तुलना की आवश्यकता होती है।
+एन आइटम वाली सूची के लिए, सबसे अच्छा मामला तब होता है जब मान सूची के पहले तत्व के बराबर होता है, उस स्थिति में केवल तुलना की आवश्यकता होती है। सबसे खराब स्थिति तब होती है जब मान सूची में नहीं होता है (या सूची के अंत में केवल बार होता है), उस स्थिति में n तुलना की आवश्यकता होती है।
 यदि मांगा जा रहा मूल्य सूची में k बार आता है, और सूची के सभी क्रम समान रूप से संभावित हैं, तो तुलनाओं की अपेक्षित संख्या है
@@ Line 57: / Line 51: @@
 \end{cases}
 </math>
-उदाहरण के लिए, यदि मांगा जा रहा मूल्य सूची में एक बार आता है, और सूची के सभी क्रम समान रूप से संभावित हैं, तो तुलनाओं की अपेक्षित संख्या है <math>\frac{n + 1}2</math>. हालाँकि, यदि यह ज्ञात है कि यह एक बार होता है, तो अधिकतम n - 1 तुलनाओं की आवश्यकता होती है, और तुलनाओं की अपेक्षित संख्या है
+उदाहरण के लिए, यदि मांगा जा रहा मूल्य सूची में बार आता है, और सूची के सभी क्रम समान रूप से संभावित हैं, तो तुलनाओं की अपेक्षित संख्या है <math>\frac{n + 1}2</math>. हालाँकि, यदि यह ज्ञात है कि यह बार होता है, तो अधिकतम n - 1 तुलनाओं की आवश्यकता होती है, और तुलनाओं की अपेक्षित संख्या है
 :<math>\displaystyle\frac{(n + 2)(n-1)}{2n}</math>
 (उदाहरण के लिए, n = 2 के लिए यह 1 है, जो एकल if-then-else निर्माण के अनुरूप है)।
@@ Line 79: / Line 73: @@
    }}
 </ref>
 ==आवेदन==
 रैखिक खोज को लागू करना आम तौर पर बहुत सरल होता है, और व्यावहारिक होता है जब सूची में केवल कुछ तत्व होते हैं, या बिना क्रम वाली सूची में एकल खोज करते समय।
-जब एक ही सूची में कई मानों को खोजना होता है, तो तेज़ विधि का उपयोग करने के लिए अक्सर सूची को पूर्व-संसाधित करना पड़ता है। उदाहरण के लिए, कोई सूची को [[ सॉर्ट करें (कंप्यूटिंग) ]] कर सकता है और बाइनरी खोज एल्गोरिदम का उपयोग कर सकता है, या इससे एक कुशल खोज डेटा संरचना बना सकता है। क्या सूची की सामग्री बार-बार बदलती रहती है, बार-बार पुनर्संगठन करने से अधिक परेशानी हो सकती है।
+जब ही सूची में कई मानों को खोजना होता है, तो तेज़ विधि का उपयोग करने के लिए अक्सर सूची को पूर्व-संसाधित करना पड़ता है। उदाहरण के लिए, कोई सूची को [[ सॉर्ट करें (कंप्यूटिंग) |सॉर्ट करें (कंप्यूटिंग)]] कर सकता है और बाइनरी खोज एल्गोरिदम का उपयोग कर सकता है, या इससे कुशल खोज डेटा संरचना बना सकता है। क्या सूची की सामग्री बार-बार बदलती रहती है, बार-बार पुनर्संगठन करने से अधिक परेशानी हो सकती है।
 परिणामस्वरूप, भले ही सिद्धांत रूप में अन्य खोज एल्गोरिदम रैखिक खोज (उदाहरण के लिए बाइनरी खोज) से तेज़ हो सकते हैं, व्यवहार में यहां तक कि मध्यम आकार के सरणियों (लगभग 100 आइटम या उससे कम) पर भी किसी और चीज़ का उपयोग करना संभव नहीं हो सकता है। बड़े सरणियों पर, यदि डेटा पर्याप्त बड़ा है तो अन्य, तेज़ खोज विधियों का उपयोग करना ही समझ में आता है, क्योंकि डेटा को तैयार (सॉर्ट) करने का प्रारंभिक समय कई रैखिक खोजों के बराबर होता है।<ref>{{Cite web |first=Adam |last=Horvath |url=http://blog.teamleadnet.com/2012/02/quicksort-binary-search-and-linear.html |title=.NET और मोनो प्लेटफ़ॉर्म पर बाइनरी खोज और रैखिक खोज प्रदर्शन|access-date=19 April 2013 }}</ref>
 ==यह भी देखें==
 * [[टर्नरी खोज]]
@@ Line 95: / Line 85: @@
 ==संदर्भ==
 ===उद्धरण===
 {{Reflist}}
 ===कार्य===

Anonymous

Search

रेखीय खोज: Difference between revisions

Namespaces

More

Page actions

Revision as of 13:51, 5 July 2023

Contents

एल्गोरिदम

बुनियादी एल्गोरिदम

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

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

विश्लेषण

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

आवेदन

यह भी देखें

संदर्भ

उद्धरण

कार्य

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

रेखीय खोज: Difference between revisions

Revision as of 13:51, 5 July 2023

एल्गोरिदम

बुनियादी एल्गोरिदम

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

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

विश्लेषण

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

आवेदन

यह भी देखें

संदर्भ

उद्धरण

कार्य

Navigation

Wiki tools

Page tools

Other projects

Hidden categories