सामग्री

• तुलना चार्ट
• रेखीय शोध व्याख्या
• बायनरी सर्च ची व्याख्या
• निष्कर्ष

रेखीय शोध आणि बायनरी शोध या दोन पद्धती आहेत ज्या अ‍ॅरेसाठी वापरल्या जातात शोधत आहे घटक. शोध म्हणजे कोणत्याही क्रमाने किंवा यादृच्छिकपणे संग्रहित केलेल्या घटकांच्या सूचीमध्ये घटक शोधण्याची प्रक्रिया.

रेखीय शोध आणि बायनरी शोध मधील मुख्य फरक असा आहे की बायनरी शोध घटकांच्या क्रमानुसार यादीतून घटक शोधण्यासाठी कमी वेळ घेते. म्हणून हे अनुमानित केले जाते की बायनरी शोध पद्धतीची कार्यक्षमता रेखीय शोधापेक्षा जास्त आहे.

या दोहोंमधील आणखी एक फरक म्हणजे बायनरी शोधासाठी पूर्व शर्त आहे, म्हणजे घटक असणे आवश्यक आहे क्रमवारी लावली रेखीय शोधात असताना अशी कोणतीही पूर्वस्थिती नाही. जरी दोन्ही शोध पद्धती वेगवेगळ्या तंत्रांचा वापर करतात ज्या खाली चर्चा केल्या आहेत.

1. तुलना चार्ट
2. व्याख्या
3. मुख्य फरक
4. निष्कर्ष

तुलना चार्ट

तुलना करण्यासाठी आधार	रेषात्मक शोध	बायनरी शोध
वेळ कॉम्प्लेक्सिटी	ओ (एन)	ओ (लॉग 2 एन)
सर्वोत्तम केस वेळ	प्रथम घटक ओ (1)	केंद्र घटक ओ (1)
अ‍ॅरेसाठी पूर्व शर्त	आवश्यक नाही	अ‍ॅरे क्रमवारीत असणे आवश्यक आहे
घटकांची संख्या एन साठी सर्वात वाईट प्रकरण	एन तुलना आवश्यक आहे	फक्त लॉग नंतर निष्कर्ष काढू शकता2एन तुलना
यावर अंमलबजावणी होऊ शकते	अ‍ॅरे आणि लिंक्ड यादी	दुवा साधलेल्या सूचीवर थेट लागू केला जाऊ शकत नाही
ऑपरेशन घाला	सूचीच्या शेवटी सहजपणे घातले	क्रमवारी लावलेल्या सूचीची देखरेख करण्यासाठी त्यास योग्य ठिकाणी घालाण्यासाठी प्रक्रिया आवश्यक आहे.
अल्गोरिदम प्रकार	निसर्गामध्ये Iterative	विभाजित करा आणि निसर्गावर विजय मिळवा
उपयोगिता	वापरण्यास सुलभ आणि कोणत्याही ऑर्डर केलेल्या घटकांची आवश्यकता नाही.	काहीही झाले तरी अल्गोरिदम आणि घटक क्रमाने व्यवस्थित केले पाहिजेत.
कोडच्या ओळी	कमी	अधिक

रेखीय शोध व्याख्या

रेखीय शोधात अ‍ॅरेचा प्रत्येक घटक लॉजिकल क्रमाने एक-एक करून परत मिळविला जातो आणि तो इच्छित घटक आहे की नाही याची तपासणी केली जाते. सर्व घटकांमध्ये प्रवेश केला असल्यास आणि इच्छित घटक सापडला नाही तर शोध अयशस्वी होईल. सर्वात वाईट परिस्थितीत, आपल्याला अ‍ॅरेच्या आकाराचे निम्मे अर्धे स्कॅन करावे लागतील अशा सरासरी केसांची संख्या (एन / 2).

म्हणून रेखीय शोध तंत्र म्हणून परिभाषित केले जाऊ शकते जे दिलेली आयटम शोधण्यासाठी अ‍ॅरेचा क्रमवारपणे फिरत असेल. खाली दिलेला प्रोग्रॅम सर्चचा वापर करून अ‍ॅरेच्या घटकाचा शोध घेईल.

कार्यक्षमता रेषात्मक शोध

शोध सारणीमध्ये रेकॉर्ड शोधण्यात केलेला वेळ वापर किंवा तुलनांची संख्या तंत्राची कार्यक्षमता निश्चित करते. इच्छित रेकॉर्ड शोध सारणीच्या पहिल्या स्थानावर असल्यास, नंतर केवळ एक तुलना केली जाईल. जेव्हा इच्छित रेकॉर्ड शेवटचा असेल तर एन तुलना करावी लागेल. रेकॉर्ड शोध कोठेत कुठेतरी सादर करायचे असल्यास, सरासरी, तुलनांची संख्या (एन + 1/2) असेल. या तंत्राची सर्वात वाईट कार्यक्षमता म्हणजे ओ (एन) म्हणजे अंमलबजावणीच्या क्रमाचा क्रम.

सी कार्यक्रम रेखीय शोध तंत्रासह घटक शोधण्यासाठी.

# समाविष्ट करा # समाविष्ट करा शून्य मुख्य () a इंट अ, एन, आय, आयटम, लोकल = -1; clrscr (); f ("element n घटकाची संख्या प्रविष्ट करा:"); स्कॅनफ ("% d", & n); f ("संख्या प्रविष्ट करा: n"); (i = 0; i <= n-1; i ++) {स्कॅनफ ("% d", आणि ए) साठी; } f (" n शोधण्यासाठी नंबर प्रविष्ट करा:"); स्कॅनफ ("% d", आणि आयटम); (i = 0; i <= n-1; i ++) {जर (आयटम == a) {लोक = i; ब्रेक }} if (loc> = 0) {f (" n% d स्थिती% d मध्ये आढळली:", आयटम, लोकॅ +1); } else {f (" n आयटम विद्यमान नाही"); } गेच (); }

बायनरी सर्च ची व्याख्या

बायनरी शोध एक अत्यंत कार्यक्षम अल्गोरिदम आहे. हे शोध तंत्र कमीतकमी शक्य तुलनांमध्ये दिलेल्या आयटम शोधण्यात कमी वेळ घालवते. बायनरी शोध घेण्यासाठी प्रथम अ‍ॅरे घटकांची क्रमवारी लावावी लागेल.

या तंत्रज्ञानामागील तर्क खाली दिले आहे:

• प्रथम अ‍ॅरेचा मधला घटक शोधा.
• अ‍ॅरेचा मध्यम घटक शोधला जाणार्‍या घटकाशी तुलना केली जाते.

तीन प्रकरणे उद्भवू शकतात:

1. जर घटक आवश्यक घटक असेल तर शोध यशस्वी आहे.
2. जेव्हा घटक इच्छित आयटमपेक्षा कमी असतो, तेव्हा अ‍ॅरेच्या केवळ पहिल्या सहामाहीत शोधा.
3. ते इच्छित घटकापेक्षा मोठे असल्यास अ‍ॅरेच्या दुसर्‍या सहामाहीत शोधा.

एखादा घटक सापडल्याशिवाय किंवा शोध क्षेत्रात संपत नाही तोपर्यंत त्याच चरणांची पुनरावृत्ती करा. या अल्गोरिदममध्ये, प्रत्येक वेळी शोध क्षेत्र कमी होत आहे. म्हणून तुलनाची संख्या सर्वाधिक लॉग (एन + 1) वर आहे. परिणामी, रेखीय शोधाच्या तुलनेत हे कार्यक्षम अल्गोरिदम आहे, परंतु बायनरी शोध करण्यापूर्वी अ‍ॅरेची क्रमवारी लावावी लागते.

सी कार्यक्रम बायनरी शोध तंत्रासह घटक शोधण्यासाठी.

# समाविष्ट करा शून्य मुख्य () {इंट i, भीक, शेवट, मध्य, एन, शोध, अ‍ॅरे; f ("घटकांची संख्या प्रविष्ट करा n"); स्कॅनफ ("% d", & n); f ("% d संख्या प्रविष्ट करा n", n); (i = 0; i <n; i ++) स्कॅनफ ("% d", & अ‍ॅरे) साठी; f ("शोधण्यासाठी क्रमांक प्रविष्ट करा n"); स्कॅनफ ("% d", आणि शोध); भीक = 0; शेवट = एन - 1; मध्यम = (भीक + शेवट) / 2; असताना (भीक <= अंत) {if (अ‍ॅरे <शोध) भिख = मध्यम + 1; अन्यथा (अ‍ॅरे == शोध) {एफ ("शोध यशस्वी झाला. location n% d स्थान% d वर आढळला. n", शोध, मध्य +1); ब्रेक end अन्य अंत = मध्यम - 1; मध्यम = (भीक + शेवट) / 2; } if (भीक> शेवट) f ("शोध अयशस्वी झाला आहे!% d सूचीमध्ये उपस्थित नाही.; n", शोध); गेच (); }

1. रेषात्मक शोध हा स्वभावानुसार पुनरावृत्ती करणारा आहे आणि अनुक्रमिक दृष्टीकोन वापरतो. दुसरीकडे, बायनरी शोध विभाजित आणि विजय जिंकण्याचा दृष्टीकोन लागू करते.
2. रेखीय शोधांची वेळ जटिलता ओ (एन) आहे तर बायनरी शोधात ओ (लॉग) आहे₂एन)
3. रेखीय शोधातील सर्वोत्तम केस वेळ प्रथम घटकासाठी म्हणजे, ओ (1) आहे. त्याउलट, बायनरी शोधात, ते मध्यम घटकासाठी आहे, म्हणजे, ओ (1)
4. रेखीय शोधात, घटक शोधण्यासाठी सर्वात वाईट घटना म्हणजे तुलनाची संख्या. याउलट तो लॉग आहे₂बायनरी शोधासाठी तुलनाची संख्या
5. रेखीय शोध अ‍ॅरेमध्ये तसेच लिंक्ड लिस्टमध्ये लागू केला जाऊ शकतो तर बाइनरी सर्च थेट लिंक्ड लिस्टवर लागू केला जाऊ शकत नाही.
6. आम्हाला माहित आहे की बायनरी शोधासाठी क्रमवारी लावलेल्या अ‍ॅरेची आवश्यकता आहे कारण त्यास क्रमवारी लावलेल्या सूचीची देखरेख करण्यासाठी त्यास योग्य त्या ठिकाणी समाविष्ट करणे आवश्यक आहे. उलट रेषात्मक शोधासाठी क्रमवारी लावलेल्या घटकांची आवश्यकता नसते, म्हणून घटक सूचीच्या शेवटी सहज समाविष्ट केले जातात.
7. रेखीय शोध वापरणे सोपे आहे आणि कोणत्याही ऑर्डर केलेल्या घटकांची आवश्यकता नाही. दुसरीकडे, बायनरी शोध अल्गोरिदम तथापि अवघड आहे आणि घटकांची क्रमाने सुसंगत व्यवस्था केली आहे.

निष्कर्ष

दोन्ही रेखीय आणि बायनरी शोध अल्गोरिदम अनुप्रयोगानुसार उपयुक्त ठरू शकतात. जेव्हा अ‍ॅरे डेटा रचना असते आणि घटकांची क्रमवारी लावलेली व्यवस्था केली जाते, तेव्हा बायनरी शोध प्राधान्य दिले जाते द्रुतशोधत आहे. जर दुवा साधलेली यादी डेटाची रचना असेल तर त्या घटकांची व्यवस्था कशी केली जात नाही, बायनरी सर्च अल्गोरिदमच्या प्रत्यक्ष अंमलबजावणीच्या अनुपलब्धतेमुळे रेखीय शोध स्वीकारला जातो.

टिपिकल बायनरी सर्च अल्गोरिदम लिंक केलेल्या यादीमध्ये काम करता येणार नाही कारण दुवा साधलेली यादी निसर्गात गतिमान आहे आणि मध्यम घटक प्रत्यक्षात नेमलेला आहे हे माहित नाही. म्हणूनच, बाइनरी सर्च अल्गोरिदमच्या भिन्नतेची रचना करण्याची आवश्यकता आहे जे दुवा साधलेल्या सूचीवर देखील कार्य करू शकतात कारण बायनरी शोध रेषीय शोधापेक्षा अंमलबजावणीत वेगवान आहे.