Searching Techniques-in Hindi
Linear Search-in Hindi
Linear search searching की सबसे सरल विधि होती है। इस विधि में सर्वप्रथम list के पहले item की तुलना search key से करते हैं। यदि पहला item search key से match कर जाता है तो search operation यही पर successful हो जाता है और हम पहले item के location को आउटपुट कर देते हैं। और यदि पहला item search key से match नही करता है तो हम search operation को continue रखते हैं और list ले दूसरे item की तुलना search key से करते हैं और इसी प्रक्रिया को टैब तक करते चलते हैं जब तक कि खोज जा रहा item नही मिल जाता है।
Linear seach operation दो ही स्थिति में stop होता है। पहला जब खोजा जा रहा item list में उपस्थित हो तो उसी स्थान पर successful होकर stop होता है। दूसरा जब खोजा जा रहा item list में उपस्थित न हो तो अंत मे unsuccessful होकर stop होता है।
The complexity of Linear Search
Linear search की complexity इसके द्वारा list में search key की ढूढ़ने में किए गए comparisons की कुल संख्या से ज्ञात की जाती है जो n एवं search key दोनो पर निर्भर करती है:
Worst Case
Linear search के algorithm से स्पष्ट है कि इसकी सहायता से किसी list में search key को ढूढ़ने में सबसे अधिक समय तब लगेगा जब search key list के अंत मे स्थित होगा क्योंकि इस स्थिति में हमें पूरे n comparison करने होंगे। अतः linear search की worst case complexity होगी:
F(n)=n=O(n)
Best Case
Linear search के algorithm से स्पष्ट है कि इसकी सहायता से किसी list में search key को ढूढ़ने में सबसे कम समय तब लगेगा जब search key list की शुरुआत में स्थित होगा क्योंकि इस स्थिति में हमें केवल 1 comparison करना होगा। अतः linear search की best case complexity होगी:
F(n)=1=Ω(1)
Average Case
Average case complexity ज्ञान करते समय हम यह मान लेते हैं कि search key list में किसी भी स्थान पर स्थित हो सकता है। अतः इसे ढूढ़ने में comparisons की कुल संख्या 1,2,3…..n में से कोई भी एक हो सकता है। चुकी प्रत्येक संख्या की प्रायिकता 1/n है अतः linear search की average case complexity होगी:
F(n) = 1/n+2/n+3/n+….n/n
= 1/n(1+2+3+…n)
= 1/n.n(n+1)/2
= (n+1)/2
= θ(n)
Binary Search-in Hindi
Binary Search किसी बड़े list में searching की अच्छी विधि होती है। इसके लिए list का sorted होना अनिवार्य होता है साथ ही list के middle element की direct accessing भी जरूरी होती है।
इस विधि में सर्वप्रथम list के middle item की तुलना search key से करते हैं। यदि middle item search key से match कर जाता है तो search operation यही पर successful हो जाता है और हम middle item के location को आउटपुट कर देते हैं और यदि middle item search key से match नही करता है तो हम search operation को continue रखते हैं और यह जाँच करते हैं कि middle item search key से छोटा है या बड़ा? इससे हमें यह पता चल जाता है कि खोजा जा रहा item list के किसी half में उपस्थित होगा।
अतः अब हम केवल correct half के middle item की तुलना search key से करते हैं और इसी प्रक्रिया को तब तक करते चले जाते हैं जब तक कि खोजा जा रहा item नही मिल जाता है। Binary Search operation दो ही स्थिति में stop होता है। पहला जब खोज जा रहा item list में उपस्थित हो तो उसी स्थान पर successful होकर stop होता है। दूसरा जब खोज जा रहा item list में उपस्थित न हो और low, high से बड़ा हो जाए तो अंत मे unsuccessful होकर stop होता है।
The complexity of Binary Search
Binary search की complexity इसके द्वारा list में search key की ढूढ़ने में किए गए comparisons की कुल संख्या से ज्ञात की जाती है जो n एवं search key दोनो पर निर्भर करती है। इसमें प्रत्येक comparison के बाद list को आधा कर दिया जाता है। इसलिये इसमें complexity ज्ञात करने के लिए यह पता लगाया जाता है कि हम n को कितने बार 2 से भाग दे कि हमारे पास अंत मे 1 बचे अतः binary search की complexity होगी:
Difference Between Linear and Binary Search
Linear Search | Binary Search |
---|---|
(1) Linear search में search operation list के first element से प्रारंभ होता है। | (1) Binary search में search operation list के middle element से प्रारंभ होता है। |
(2) इसमें एक-एक करके list के प्रत्येक element को check किया जाता है जब तक कि search key न मिल जाए या अंतिम element तक न पहुँच जाए। | (2) इसमें करके list के middle element को check किया जाता है और प्रत्येक बार मे list को आधा कर दिया जाता है जब तक कि search key न मिल जाए या low, high से बड़ा न हो जाए। |
(3) इसके लिए list का sorted होना आवश्यक नहीं होता है और middle element की direct accessing भी जरूरी नही होती है। | (3) इसके लिए list का sorted होना आवश्यक होता है और middle element की direct accessing भी जरूरी नही होती है। |
(4) Array व linked list दोनों में किया जा सकता है। | (4) Array में किया जा सकता है linked list में नहीं। |
(5) बड़े list में search करने में अधिक समय लगता है। | (5) बड़े list में भी search करने में बहुत कम समय लगता है। |
(6) इसकी complexity O(n) होती है। | (6) इसकी complexity O(log2n) होती है। |