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 लिस्ट है.
| 21 | 70 | 15 | 30 | 56 | 78 | 80 |
|---|
और हमें इसमें 30 को खोजना है.
step1. दिए गये element (30) को लिस्ट के प्रथम element (21) के साथ compare (तुलना) किया जाता है।
| 21 | 70 | 15 | 30 | 56 | 78 | 80 |
|---|
दोनों एकसमान नहीं है तो हम दुसरे element में जायेंगे।
step2. 30 की लिस्ट के दुसरे element (70) के साथ तुलना करेंगे
| 21 | 70 | 15 | 30 | 56 | 78 | 80 |
|---|
दोनों एकसमान नहीं है तो हम अगले element में जायेंगे।
step3. 30 की तुलना 15 के साथ करेंगे।
| 21 | 70 | 15 | 30 | 56 | 78 | 80 |
|---|
दोनों एक समान नहीं है तो हम अगले element में जायेंगे।
step4. अब हम दिए गये element (30) की तुलना अगले element 30 के साथ करेंगे।
| 21 | 70 | 15 | 30 | 56 | 78 | 80 |
|---|
दोनों एक समान है तो हम तुलना करना बंद कर देंगे और 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 लिस्ट है.
| 3 | 5 | 11 | 17 | 25 | 30 | 32 |
|---|
हमें दिया गया element 5 है जिसे हमने लिस्ट में ढूंढना है।
step1. सबसे पहले हम दिए गये element 5 की तुलना middle element 17 से करते है।
| 3 | 5 | 11 | 17 | 25 | 30 | 32 |
|---|
दोनों एकसमान नहीं है और 5 जो है वह 17 से छोटा है।
तो हम लिस्ट के बाएं वाले भाग (छोटे वाले भाग) में ही search करेंगे।
| 3 | 5 | 11 |
|---|
step2. दिए गये element 5 को middle element 5 के साथ compare करेंगे।
| 3 | 5 | 11 |
|---|
दोनों एकसमान है तो हम तुलना करना बंद कर देंगे। और index 1 रिटर्न करेंगे।