रैखिक खोज

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

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

प्रणाली

बुनियादी प्रणाली

मान लें कि हमें θ तत्वों की एक सूची दी गई है । Σ_० , Σ_१ , .... , Σ_θ-१ इस सूची के तत्व हैं और λ वो वस्तु हैं जो हमें सूचि में खोजनी हैं । खोजने की प्रणाली नीचे वर्णित है :

1. प्रारंभ में β का मूल्य ० है।
2. यदि Σ_β = λ, तो खोज सफलतापूर्वक समाप्त हो जाती है; β उत्तर है।
3. β को १ से बढ़ाइए
4. यदि β < θ,  दूसरे कदम पे लौटिये । अन्यथा, खोज असफल रूप से समाप्त हो जाती है।

"सेंटिनल" के साथ

उपरोक्त मूल प्रणाली हर पुनरावृत्ति में दो तुलना करता है: एक यह जांचने के लिए कि क्या ली टी के बराबर है, और दूसरा यह जांचने के लिए कि क्या बीटा तीता से कम है। सूची में एक और त्तत्त्व Σ_θ, जो खोजे जाने वाले वस्तु के समान होता है,  जोड़कर (एक सेंटिनल) हम दूसरी तुलना को खोज के अंत तक हटाकर प्रणाली को और तेज बना सकते हैं। यदि खोजा जाने वाला वस्तु सूची का हिस्सा नहीं है तो खोज सेंटिनल तक पहुंच जाएगी।

1. प्रारंभ में β का मूल्य ० है।
2. यदि Σ_β = λ, तो तो चौथे कदम पे जाइए।
3. β को १ से बढ़ाइए और दूसरे कदम पे लौटिये।
4. यदि β < θ,  खोज सफलतापूर्वक समाप्त हो गई और उत्तर β है । अन्यथा, खोज असफल रूप से समाप्त हो जाती है।

विश्लेषण

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

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

<math>

\begin{cases}

 \theta                  & \mbox{if } \pi = 0 \\[5pt]
 \displaystyle\frac{\theta + 1}{\pi + 1} & \mbox{if } 1 \le \pi \le \theta.

\end{cases} </math>

निष्कर्ष में, रैखिक खोज की सबसे खराब पारिस्थिति और उसकी अपेक्षित लागत, दोनों O(θ) हैं।

असमान संभावनाएँ

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

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

उपयोग

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

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

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