Searching (सर्चिंग):- जैसा कि आपको पता ही होगा सर्चिंग का अर्थ है “ढूंढना” या “खोजना” । डेटा स्ट्रक्चर में ‘searching’ वह प्रक्रिया है जिसमें किसी element को लिस्ट में खोजा जाता है जो कि एक या एक से अधिक condition को संतुष्ट करता हो।

Types of Searching :-

डेटा स्ट्रक्चर में searching के लिए हम दो तकनीकों का प्रयोग करते हैं जो कि निम्नलिखित हैं:-

1. linear search (लीनियर सर्च)
2.  binary search (बाइनरी सर्च)

1. Linear search

इसको sequential search भी कहते है। इस searching तकनीक में दिए गये डेटा element को तब तक एक एक करके लिस्ट के प्रत्येक element के साथ compare किया जाता है जब तक कि element मिल नहीं जाता। इसमें सबसे पहले दिए गये element को लिस्ट के प्रथम element के साथ compare किया जाता है यदि दोनों element एक समान है तो वह index value रिटर्न करता है नहीं तो -1 रिटर्न करता है.
फिर इसके बाद दिए गये element को लिस्ट के दुसरे element के साथ compare किया जाता है. यदि दोनों element समान है तो वह index value रिटर्न करता है नहीं तो -1 रिटर्न करता है।

इसी प्रकार पूरी लिस्ट को compare किया जाता है जब तक कि element मिल नहीं जाता है।अगर पूरी लिस्ट compare करने के बाद भी element नहीं मिलता है तो सर्च unsuccessful हो जाएगा। यह सबसे सरल searching तकनीक है परन्तु इसमें समय बहुत लगता है। क्योंकि linear search की औसत case complexity O(n) है।

linear search algorithm:-

step1        i=1 {i=0}
step2         if i>n, go to step 7
step3         if A[i]=x, go to step 6
step4         i=i+1
step5         go to step 2
step6         return i
step7         return -1
step8         exit

उदाहरण के द्वारा हम इसे आसानी से समझ सकते है.

माना कि हमारे पास निम्नलिखित array लिस्ट है.

21701530567880

और हमें इसमें 30 को खोजना है.

step1.  दिए गये element (30) को लिस्ट के प्रथम element (21) के साथ compare (तुलना) किया जाता है।

21701530567880

दोनों एकसमान नहीं है तो हम दुसरे element में जायेंगे।

step2.  30 की लिस्ट के दुसरे element (70) के साथ तुलना करेंगे

21701530567880

दोनों एकसमान नहीं है तो हम अगले element में जायेंगे।

step3. 30 की तुलना 15 के साथ करेंगे।

21701530567880

दोनों एक समान नहीं है तो हम अगले element में जायेंगे।

step4.  अब हम दिए गये element (30) की तुलना अगले element 30 के साथ करेंगे।

21701530567880

दोनों एक समान है तो हम तुलना करना बंद कर देंगे और index 3 रिटर्न करेंगे।

Binary Search

जब कोई बड़ा डाटा स्ट्रक्चर होता है तो linear search में बहुत अधिक समय लग जाता है। इसलिए linear search की कमी को दूर करने के लिए binary search को विकसित किया गया। binary search बहुत ही तेज searching अल्गोरिथम है जिसकी time complexity O(log n) है। यह divide & conquer सिद्धांत पर आधारित है। binary search केवल उसी लिस्ट में की जा सकती है जो कि sorted (क्रमानुसार) हों. इसका प्रयोग ऐसी लिस्ट में नहीं कर सकते जो कि sorted order में नहीं है।

इस सर्चिंग तकनीक में दिए गये element की लिस्ट के middle element के साथ तुलना की जाती है। यदि दोनों एकसमान है तो वह index value रिटर्न करता है। यदि एक समान नहीं है तो हम check करते है कि दिया गया element जो है वह middle element से बड़ा है या छोटा। यदि वह छोटा है तो हम लिस्ट के छोटे भाग में यही प्रक्रिया दोहराएंगे। और यदि वह बड़ा है तो हम लिस्ट के बड़े भाग में यही प्रक्रिया दोहराएंगे। और यह तब तक करेंगे जब तक कि element मिल नहीं जाता।

उदाहरण:- इसको हम भलीभांति उदाहरण के द्वारा समझ सकते है।
माना हमारे पास निम्नलिखित array लिस्ट है.

351117253032

हमें दिया गया element 5 है जिसे हमने लिस्ट में ढूंढना है।

step1. सबसे पहले हम दिए गये element 5 की तुलना middle element 17 से करते है।

351117253032

दोनों एकसमान नहीं है और 5 जो है वह 17 से छोटा है।

तो हम लिस्ट के बाएं वाले भाग (छोटे वाले भाग) में ही search करेंगे।

3511

step2. दिए गये element 5 को middle element 5 के साथ compare करेंगे।

3511

दोनों एकसमान है तो हम तुलना करना बंद कर देंगे। और index 1 रिटर्न करेंगे।


Leave a Reply