उदाहरण के साथ द्विआधारी खोज एल्गोरिदम

इससे पहले कि हम बाइनरी खोज सीखें, आइए जानें:

खोज क्या है?

खोज एक उपयोगिता है जो अपने उपयोगकर्ता को डेटाबेस के अंदर रखे दस्तावेजों, फाइलों, मीडिया या किसी अन्य प्रकार के डेटा को खोजने में सक्षम बनाती है। खोज रिकॉर्ड के साथ मापदंड से मेल खाने और उपयोगकर्ता को प्रदर्शित करने के सरल सिद्धांत पर काम करती है। इस तरह, सबसे बुनियादी खोज फ़ंक्शन काम करता है।

बाइनरी सर्च क्या है?

एक द्विआधारी खोज एक उन्नत प्रकार का खोज एल्गोरिथ्म है जो वस्तुओं की क्रमबद्ध सूची से डेटा को पाता है और प्राप्त करता है। इसके मुख्य कार्य सिद्धांत में सूची में डेटा को आधे तक विभाजित करना शामिल है जब तक कि आवश्यक मूल्य स्थित नहीं है और खोज परिणाम में उपयोगकर्ता को प्रदर्शित किया जाता है। बाइनरी खोज को आमतौर पर आधे अंतराल की खोज या एक लघुगणक खोज के रूप में जाना जाता है ।

इस एल्गोरिथ्म ट्यूटोरियल में, आप सीखेंगे:

• खोज क्या है?
• बाइनरी सर्च क्या है?
• बाइनरी सर्च कैसे काम करता है?
• उदाहरण बाइनरी खोज
• हमें बाइनरी सर्च की आवश्यकता क्यों है?

बाइनरी सर्च कैसे काम करता है?

बाइनरी खोज निम्नलिखित तरीके से काम करती है:

• खोज प्रक्रिया डेटा के क्रमबद्ध सरणी के मध्य तत्व का पता लगाकर आरंभ करती है
• उसके बाद, तत्व के साथ कुंजी मूल्य की तुलना की जाती है
• यदि कुंजी मान मध्य तत्व से छोटा है, तो खोज तुलना और मिलान के लिए मध्य तत्व के ऊपरी मूल्यों का विश्लेषण करती है
• मामले में यदि मुख्य मूल्य मध्य तत्व से अधिक है, तो खोज तुलना और मिलान के लिए मध्य तत्व के निचले मूल्यों का विश्लेषण करती है

उदाहरण बाइनरी खोज

आइए हम एक शब्दकोश के उदाहरण को देखें। यदि आपको एक निश्चित शब्द खोजने की आवश्यकता है, तो कोई भी प्रत्येक शब्द क्रमबद्ध तरीके से नहीं जाता है, लेकिन आवश्यक शब्द खोजने के लिए निकटतम शब्दों को यादृच्छिक रूप से खोजता है।

उपरोक्त छवि निम्नलिखित दर्शाती है:

1. आपके पास 10 अंकों की एक सरणी है, और तत्व 59 को खोजने की आवश्यकता है।
2. सभी तत्वों को 0 - 9 से सूचकांक के साथ चिह्नित किया गया है। अब, सरणी के मध्य की गणना की जाती है। ऐसा करने के लिए, आप अनुक्रमणिका के बाएँ और दाएँ मान लेते हैं और उन्हें 2 से विभाजित करते हैं। परिणाम 4.5 है, लेकिन हम फर्श का मान लेते हैं। इसलिए मध्य 4 है।
3. एल्गोरिथ्म सभी तत्वों को बीच (4) से सबसे कम बाउंड तक ड्रॉप करता है क्योंकि 59 24 से अधिक है, और अब सरणी केवल अन्य तत्वों के साथ छोड़ दी गई है।
4. अब, 59 45 से अधिक है और 63 से कम है। मध्य 7. है। इसलिए दायां सूचकांक मूल्य मध्य हो जाता है - 1, जो 6 के बराबर होता है, और बायां सूचकांक मूल्य पहले की तरह ही रहता है, जो 5 है।
5. इस बिंदु पर, आप जानते हैं कि 59 45 के बाद आता है। इसलिए, बाएं सूचकांक, जो 5 है, साथ ही मध्य हो जाता है।
6. ये पुनरावृत्तियों तब तक जारी रहती हैं जब तक कि सरणी केवल एक तत्व तक कम नहीं हो जाती है, या पाया जाने वाला आइटम सरणी के बीच में हो जाता है।

उदाहरण 2

आइए द्विआधारी खोज को समझने के लिए निम्नलिखित उदाहरण देखें

1. आपके पास 2 से 20 तक के सॉर्ट किए गए मान हैं और 18 खोजने की आवश्यकता है।
2. निचली और ऊपरी सीमाओं का औसत (l + r) / 2 = 4. है जो खोजा जा रहा है वह मध्य से अधिक है जो 4 है।
3. मध्य से कम सरणी मान खोज से हटा दिए जाते हैं और मध्य मान 4 से अधिक मान खोजे जाते हैं।
4. यह एक आवर्तक विभाजन प्रक्रिया है जब तक कि खोज की जाने वाली वास्तविक वस्तु नहीं मिल जाती।

हमें बाइनरी सर्च की आवश्यकता क्यों है?

निम्नलिखित कारणों से द्विआधारी खोज को खोज एल्गोरिथ्म के रूप में उपयोग करने के लिए बेहतर विकल्प बनाया जाता है:

• किसी भी प्रकार के डेटा के आकार के आधार पर बाइनरी खोज कुशलता से काम करता है
• किसी अनुक्रम में डेटा के माध्यम से खोज करने के बजाय, बाइनरी एल्गोरिथ्म आवश्यक तत्व को खोजने के लिए डेटा को यादृच्छिक रूप से एक्सेस करता है। यह खोज चक्रों को छोटा और अधिक सटीक बनाता है।
• बाइनरी खोज समानता क्रमों का उपयोग करने की तुलना में एक आदेश सिद्धांत के आधार पर सॉर्ट किए गए डेटा की तुलना करती है, जो धीमी और ज्यादातर गलत हैं।
• खोज के प्रत्येक चक्र के बाद, एल्गोरिथ्म सरणी के आकार को आधे में विभाजित करता है इसलिए अगले पुनरावृत्ति में यह सरणी के शेष आधे हिस्से में ही काम करेगा

सारांश

• खोज एक उपयोगिता है जो अपने उपयोगकर्ता को दस्तावेज़ों, फ़ाइलों और अन्य प्रकार के डेटा की खोज करने में सक्षम बनाती है। एक द्विआधारी खोज एक उन्नत प्रकार का खोज एल्गोरिथ्म है जो वस्तुओं की क्रमबद्ध सूची से डेटा को पाता है और प्राप्त करता है।
• बाइनरी खोज को आमतौर पर आधे अंतराल की खोज या एक लघुगणक खोज के रूप में जाना जाता है
• यह आवश्यक तत्व के तहत हर चलना पर सरणी को आधे में विभाजित करके काम करता है।
• बाइनरी एल्गोरिदम 2. के द्वारा बाएँ और दाएँ अनुक्रम मानों के योग को विभाजित करके सरणी के मध्य में ले जाता है। अब, एल्गोरिथ्म या तो सरणी के मध्य से तत्वों के निचले या ऊपरी बाउंड को गिराता है, जो कि मिलने वाले तत्व पर निर्भर करता है ।
• एल्गोरिथ्म आवश्यक तत्व को खोजने के लिए डेटा को बेतरतीब ढंग से एक्सेस करता है। यह खोज चक्रों को छोटा और अधिक सटीक बनाता है।
• बाइनरी खोज क्रमबद्ध डेटा के आधार पर सॉर्ट किए गए डेटा की तुलना समानता की तुलना में धीमी और गलत तरीके से करती है।
• एक बाइनरी खोज अनसोल्ड डेटा के लिए उपयुक्त नहीं है।