लीनियर सर्च
जब आप किसी बिना क्रम वाली सूची में कोई नाम ढूँढते हैं, तो आप लीनियर सर्च ही करते हैं: ऊपर से शुरू करते हैं और नीचे पढ़ते जाते हैं, जब तक नाम मिल न जाए। यह सबसे आसान सर्च है, किसी भी सूची पर काम करता है, और छोटी सूचियों के लिए अक्सर यही काफ़ी होता है।
मूल विचार
लक्ष्य की तुलना सूची के पहले मान से करें। बराबर हों तो रुक जाएँ: लक्ष्य स्थान 1 पर है। नहीं तो दूसरे मान से तुलना करें, फिर तीसरे से, और इसी तरह आगे। अगर आख़िरी मान भी मेल न खाए, तो लक्ष्य सूची में नहीं है। सूची के बारे में पहले से कुछ जानना ज़रूरी नहीं: उसका सॉर्ट होना ज़रूरी नहीं, और मान कुछ भी हो सकते हैं जिनकी बराबरी की तुलना की जा सके।
एक उदाहरण
5, 1, 4, 2, 8 में 4 खोजें। क्या 5, 4 के बराबर है? नहीं। 1? नहीं। 4? हाँ: 3 तुलनाओं के बाद स्थान 3 पर मिला। अब उसी सूची में 7 खोजें। पाँचों मान जाँचे जाते हैं और कोई मेल नहीं खाता, इसलिए 5 तुलनाओं के बाद जवाब यह है कि 7 सूची में नहीं है।
कितनी तुलनाएँ
स्थान k पर मौजूद मान को ढूँढने में k तुलनाएँ लगती हैं। अगर लक्ष्य के किसी भी स्थान पर होने की संभावना बराबर हो, तो औसतन (n + 1)/2 तुलनाएँ लगती हैं: 40 मानों के लिए 20.5। जो मान सूची में नहीं है, वह हमेशा n तुलनाएँ लेता है, क्योंकि आख़िरी तुलना के बाद ही पक्का होता है कि कोई मान मेल नहीं खाया। इसलिए लागत सूची की लंबाई के अनुपात में बढ़ती है, जिसे O(n) लिखा जाता है।
तेज़ सर्च के लिए क्रम चाहिए
लीनियर सर्च कुछ भी छोड़ नहीं सकता, क्योंकि बिना सॉर्ट की सूची में कोई भी मान कहीं भी हो सकता है। सूची सॉर्ट हो जाए तो एक तुलना बराबर या नहीं से ज़्यादा बताती है: वह बताती है कि लक्ष्य किस तरफ़ है। बाइनरी सर्च इसका इस्तेमाल करके हर चरण में सूची को आधा करता है और उसे लगभग log₂ n तुलनाएँ चाहिए, 40 मानों के लिए ज़्यादा से ज़्यादा 6। फिर भी सॉर्ट करने में भी समय लगता है, इसलिए जिस सूची में सिर्फ़ एक बार खोजना हो, उसके लिए अक्सर लीनियर सर्च ही बेहतर विकल्प है।
छोटे सुधार
सेंटिनल वाला तरीका खोजने से पहले लक्ष्य को सूची के अंत में रख देता है, ताकि लूप को सिर्फ़ मेल की जाँच करनी पड़े, सूची के अंत की नहीं। हर बार मिलने पर किसी मान को एक जगह आगे, या सबसे आगे, कर देने से बार-बार खोजे जाने वाले मान समय के साथ सस्ते हो जाते हैं। दोनों में से कोई भी n तुलनाओं वाली सबसे ख़राब स्थिति नहीं बदलता।
ख़ुद आज़माएँ
ऐप खोलें, “खोजें” में कोई मान चुनें, और आगे दबाएँ। डैश वाली रेखा लक्ष्य की ऊँचाई दिखाती है, हर मान जाँचे जाते समय हाइलाइट होता है और ख़ारिज होने पर धुँधला हो जाता है, और मेल हरा हो जाता है। पूरा एक चक्कर देखने के लिए ऐसा मान खोजें जो सूची में नहीं है, या “पहले मेल पर रुकें” बंद करें और कई मेल ढूँढने के लिए कुछ ही अलग मान इस्तेमाल करें।
अक्सर पूछे जाने वाले प्रश्न
लीनियर सर्च की टाइम कॉम्प्लेक्सिटी क्या है?
सबसे ख़राब और औसत स्थिति में O(n), और सबसे अच्छी स्थिति में O(1), जब लक्ष्य पहला मान हो। इसे कोई अतिरिक्त मेमोरी नहीं चाहिए।
लीनियर सर्च और बाइनरी सर्च में क्या फ़र्क है?
लीनियर सर्च हर मान को क्रम से जाँचता है और किसी भी सूची पर काम करता है। बाइनरी सर्च सिर्फ़ सॉर्ट की हुई सूची पर काम करता है, लेकिन हर चरण में उस हिस्से को आधा कर देता है जिसमें लक्ष्य हो सकता है, इसलिए उसे n तक के बजाय लगभग log₂ n तुलनाएँ चाहिए।
क्या लीनियर सर्च के लिए सॉर्ट की हुई सूची चाहिए?
नहीं। यही इसकी सबसे बड़ी ख़ूबी है। सॉर्ट की हुई सूची में यह उस स्थान को पार करते ही रुक सकता है जहाँ लक्ष्य होना चाहिए था, लेकिन फिर भी बाइनरी सर्च से धीमा रहता है।
लीनियर सर्च कहाँ इस्तेमाल होता है?
जहाँ भी सूचियाँ छोटी हों या सॉर्ट न हों: किसी छोटे ऐरे में कोई आइटम ढूँढना, ऐसी फ़ाइल या स्ट्रीम को स्कैन करना जिसे सिर्फ़ क्रम से पढ़ा जा सकता है, या हर एलिमेंट को किसी शर्त पर जाँचना। कई लाइब्रेरी फ़ंक्शन, जैसे JavaScript में indexOf और Python में list.index, लीनियर सर्च ही हैं।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
लीनियर सर्च आज़माएँ