रेखीय खोज

रेखीय खोज

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 का n मान या रिकॉर्ड वाले तत्व (कंप्यूटर विज्ञान) L₀ .... L_n−1, और लक्ष्य मान T, निम्नलिखित सबरूटीन लक्ष्य के सूचकांक को खोजने के लिए रैखिक खोज का उपयोग करता है T में L.

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

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

उपरोक्त मूल एल्गोरिदम प्रति पुनरावृत्ति दो तुलना करता है: एक यह जांचने के लिए कि क्या L_i टी के बराबर है, और दूसरा यह जांचने के लिए है 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 तुलना की आवश्यकता होती है।

यदि मांगा जा रहा मूल्य सूची में 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) होती है।

आवेदन

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

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

परिणामस्वरूप, भले ही सिद्धांत रूप में अन्य खोज एल्गोरिदम रैखिक खोज (उदाहरण के लिए बाइनरी खोज) से तेज़ हो सकते हैं, व्यवहार में यहां तक ​​कि मध्यम आकार के सरणियों (लगभग 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

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