बाइनरी सर्च एल्गोरिदम उदाहरण के साथ

बाइनरी सर्च सीखने से पहले आइए जानें:

खोज क्या है?

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

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

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

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

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

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

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

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

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

1. आपके पास 10 अंकों की एक सारणी है, और तत्व 59 को ढूंढना है।
2. सभी तत्वों को 0 से 9 तक के इंडेक्स से चिह्नित किया जाता है। अब, सरणी के मध्य की गणना की जाती है। ऐसा करने के लिए, आप इंडेक्स के बाएं और दाएं सबसे मान लेते हैं और उन्हें 2 से विभाजित करते हैं। परिणाम 4.5 है, लेकिन हम फ़्लोर वैल्यू लेते हैं। इसलिए बीच का मान 4 है।
3. एल्गोरिथ्म मध्य (4) से सभी तत्वों को निम्नतम सीमा तक गिरा देता है क्योंकि 59, 24 से अधिक है, और अब सारणी में केवल 5 तत्व ही बचे हैं।
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. यह एक पुनरावर्ती विभाजन प्रक्रिया है, जब तक कि खोजी जाने वाली वास्तविक वस्तु नहीं मिल जाती।

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

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

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

हमारा अगला ट्यूटोरियल जानें रेखीय खोज: Python, C++ उदाहरण

सारांश

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