बाइनरी सर्च जावा:एक गाइड

जावा में बाइनरी सर्च एल्गोरिथम कैसे लिखें

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

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

आइए शुरू करें!

द्विआधारी खोज क्या है?

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

द्विआधारी खोज एक सूची को आधे में विभाजित करके शुरू होती है। खोज तब मध्य संख्या की तुलना उस संख्या से करेगी जिसके लिए एल्गोरिथम खोज रहा है।

यदि संख्या मध्य संख्या से छोटी है, तो यह प्रक्रिया सूची के निचले आधे भाग के लिए दोहराई जाती है; अन्यथा, यह प्रक्रिया सूची के ऊपरी आधे भाग के लिए दोहराई जाती है।

बाइनरी खोज रैखिक खोजों की तुलना में अधिक कुशल हैं, एक अन्य सामान्य प्रकार की खोज। ऐसा इसलिए है क्योंकि हर बार एल्गोरिथम किसी आइटम की तलाश करता है, यह दो के कारक से खोजने के लिए आइटम की संख्या को कम कर देता है।

बाइनरी खोजों को केवल वस्तुओं की क्रमबद्ध सूची पर ही निष्पादित किया जा सकता है। इसका मतलब यह है कि अगर आपके पास पहले से कोई सॉर्ट की गई सूची नहीं है, तो आपको बाइनरी खोज चलाने से पहले सॉर्टिंग एल्गोरिदम का उपयोग करके इसे सॉर्ट करना होगा।

81% प्रतिभागियों ने कहा कि बूटकैंप में भाग लेने के बाद उन्हें अपनी तकनीकी नौकरी की संभावनाओं के बारे में अधिक आत्मविश्वास महसूस हुआ। आज ही एक बूटकैंप से मिलान करें।

बूटकैंप शुरू करने से लेकर अपनी पहली नौकरी खोजने तक, औसत बूटकैंप ग्रेड ने करियर संक्रमण में छह महीने से भी कम समय बिताया।

द्विआधारी खोज कैसे कार्य करती हैं?

बाइनरी खोजों को दो तरीकों से कार्यान्वित किया जा सकता है:पुनरावृत्त या पुनरावर्ती।

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

आप जावा रिकर्सन के लिए हमारे गाइड में रिकर्सन के बारे में अधिक जान सकते हैं।

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

निम्नलिखित सूची पर विचार करें:

हम अपनी सूची में नंबर 7 की खोज करने जा रहे हैं। शुरू करने के लिए, हम दो पॉइंटर्स सेट करने जा रहे हैं जो हमारी सूची में निम्नतम और उच्चतम पदों का प्रतिनिधित्व करते हैं:

इसके बाद, हमें अपने एरे में मध्य तत्व को खोजना होगा। हम सूत्र का उपयोग करके ऐसा कर सकते हैं:(निम्न + उच्च) / 2. इस मामले में, मध्य तत्व 8 है।

हमारा एल्गोरिथ्म तुलना करेगा कि क्या मध्य तत्व उसके बराबर है जिसके लिए हम खोज कर रहे हैं। यदि संख्याएँ समान हैं, तो हमारी खोज रुक सकती है। हम संख्या 7 की तलाश कर रहे हैं, जो 8 के बराबर नहीं है, इसलिए हमारी खोज जारी है।

हमारा एल्गोरिदम तुलना करता है कि जिस संख्या के लिए हम खोज रहे हैं वह मध्य संख्या से अधिक है या नहीं। यदि यह अधिक है, तो हमारी सूची के शीर्ष आधे भाग पर हमारी खोज फिर से शुरू हो जाएगी। यह निम्न को निम्न =मध्य_संख्या + 1 के बराबर सेट करके किया जाता है। अन्यथा, हमारी सूची के निचले आधे हिस्से पर फिर से खोज शुरू हो जाएगी।

7 (वह संख्या जिसे हम खोज रहे हैं) 8 (मध्य संख्या) से अधिक नहीं है। इसका मतलब है कि हमारा एल्गोरिथ्म हमारी सूची के निचले आधे हिस्से में खोज करेगा। हम अपने "high" मान को high =Middle_number - 1 पर सेट करके ऐसा करते हैं।

अब, हमारा एल्गोरिथ्म हमारी खोज को दोहराने जा रहा है। हम मध्य संख्या, 7 की तुलना उस संख्या से करेंगे, जिसकी हम तलाश कर रहे हैं। हम 7 नंबर की तलाश कर रहे हैं, इसलिए हमारा सर्च एल्गोरिथम रुक जाता है। हमने अपनी सूची में 7वां स्थान पाया है!

जावा बाइनरी सर्च कैसे लागू करें

हमने सिद्धांत के साथ काम किया है, इसलिए अब जो कुछ करना बाकी है वह हमारी खोज को लागू करना है। यह एक बात है कि खुद से एक सूची खोज रहे हैं और खोज रहे हैं; यह पूरी तरह से एक एल्गोरिथ्म को कोड करने के लिए एक और बात है जो हमारे लिए खोज करता है।

हम एक प्रोग्राम लिखकर शुरू करेंगे जो जावा बाइनरी सर्च को पुनरावृत्त विधि का उपयोग करके लागू करता है।

पुनरावृत्ति विधि

आइए एक फ़ंक्शन को परिभाषित करें जिसे searchItems . कहा जाता है , जो हमारी मदों की सूची के माध्यम से खोज करता है:

 क्लास बाइनरीसर्च { इंट सर्चआइटम्स (इंट ऐरे [], इंट सर्चिंगफॉर, इंट लो, इंट हाई) { जबकि (लो <=हाई) {इंट मिडिल =लो + (हाई - लो) / 2; अगर (सरणी [मध्य] ==खोज के लिए) {मध्य वापसी; } और अगर (सरणी [मध्य] <खोज के लिए) {निम्न =मध्य + 1; } और {उच्च =मध्य -1; } } वापसी -1; }} 

 यह फ़ंक्शन बाइनरी खोज का उपयोग करके हमारी मदों की सूची के माध्यम से खोज करता है। 
 
 

 हमारा फ़ंक्शन चार पैरामीटर स्वीकार करता है:वह सूची जिसके माध्यम से हम खोजना चाहते हैं (सरणी), वह आइटम जिसके लिए हम खोज रहे हैं (खोज कर रहे हैं), कम संख्या (निम्न), और उच्च संख्या (उच्च)। 
 
 

 हमारे फ़ंक्शन के अंदर हमने थोड़ी देर के लूप की घोषणा की है। जबकि "निम्न" का मान "उच्च" से कम या उसके बराबर है, लूप निष्पादित होगा। 
 
 

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

 यदि वे संख्याएँ समान हैं, तो वह मान हमारे मुख्य कार्यक्रम में वापस आ जाता है। यदि नहीं, तो हमारा प्रोग्राम यह जांचता है कि क्या मध्य स्थान पर मान उस मूल्य से कम है जिसके लिए हम खोज कर रहे हैं। यदि ऐसा है, तो एक नया निम्न मान सेट किया गया है। 
 
 

 अन्यथा, एक नया उच्च मान सेट किया जाता है ताकि हमारी सूची सूची के ऊपरी भाग में फिर से खोज सके। 
 
 

 यदि हमारा आइटम नहीं मिल सकता है, तो -1 वापस कर दिया जाता है। हम इसका उपयोग अपने मुख्य कार्यक्रम को यह बताने के लिए करेंगे कि सूची आइटम एक मिनट में नहीं मिल सकता है। 
 
 

 हमारा कोड अभी तक कुछ नहीं करता है क्योंकि हमने अपना मुख्य कार्यक्रम नहीं लिखा है। नीचे दिए गए कोड को searchItems() के नीचे जोड़ें आपके बाइनरीसर्च क्लास में कार्य करें:
 
सार्वजनिक स्थैतिक शून्य मुख्य (स्ट्रिंग args []) {बाइनरीसर्च नई खोज =नई बाइनरी खोज (); int listToSearch[] ={6, 7, 8, 9, 10}; int listLength =listToSearch.length; इंट नंबर टूफाइंड =7; int findNumber =newSearch.searchItems(listToSearch, numberToFind, 0, listLength - 1); अगर (findNumber !=-1) { System.out.println(numberToFind + "सूचकांक स्थिति पर पाया गया" + findNumber + "।"); } और { System.out.println(numberToFind + "सूची में नहीं मिला।"); } } 

 आइए अपना कोड चलाएं और देखें कि क्या होता है:
 
7 को इंडेक्स पोजीशन पर पाया गया था। हमें अपने नंबर की पोजीशन मिल गई है!
 

 हमारा मुख्य कार्यक्रम बाइनरीसर्च क्लास के इंस्टेंस को इनिशियलाइज़ करके शुरू होता है। हम इसका उपयोग कार्यक्रम में अपनी खोज बाद में शुरू करने के लिए करते हैं। फिर हम तीन चर परिभाषित करते हैं:
 
 
 
listToSearch:वह सूची जिसके माध्यम से हम खोजना चाहते हैं।
 
सूची की लंबाई:सूची की लंबाई।
 
numberToFind:वह संख्या जिसे हम सूची में खोज रहे हैं।
 
 

 एक बार जब हम इन चरों को परिभाषित कर लेते हैं, तो हम searchItems() . का उपयोग करते हैं फ़ंक्शन हमने अपनी सूची में एक संख्या खोजने के लिए पहले घोषित किया था। हम उस मान को असाइन करते हैं जो यह फ़ंक्शन "findNumber" चर पर लौटाता है। 
 
 

 यदि खोज संख्या -1 के बराबर नहीं है - जिसका अर्थ है कि हमारी संख्या मिल गई है - तो हम जिस आइटम को खोज रहे हैं उसकी अनुक्रमणिका स्थिति कंसोल पर मुद्रित होती है। अन्यथा, कंसोल पर एक संदेश छपा होता है जो बताता है कि नंबर नहीं मिल सका।
 
पुनरावर्ती विधि
 

 एक द्विआधारी खोज को लागू करने के लिए एक पुनरावर्ती दृष्टिकोण लिया जा सकता है। यह वह जगह है जहां आप एक फ़ंक्शन लिखते हैं जो एक निर्दिष्ट आइटम मिलने तक स्वयं को कॉल करता है। 
 
 

 आइए एक फ़ंक्शन को परिभाषित करके शुरू करें जो हमारी बाइनरी खोज को पुनरावर्ती रूप से करता है:
 
 क्लास बाइनरीसर्च { इंट सर्चआइटम्स (इंट ऐरे [], इंट सर्चिंगफॉर, इंट लो, इंट हाई) {अगर (हाई> =लो) {इंट मिडिल =लो + (हाई - लो) / 2; अगर (सरणी [मध्य] ==खोज के लिए) {मध्य वापसी; } और अगर (सरणी [मध्य] <खोज के लिए) { searchItems (सरणी, searchFor, मध्य + 1, उच्च); } और { searchItems (सरणी, searchFor, कम, मध्य -1); } } वापसी -1; }} 

 यह फ़ंक्शन हमारी बाइनरी खोज को एक अलग तरीके से लागू करता है। थोड़ी देर के लूप का उपयोग करने के बजाय, हम if . का उपयोग करते हैं यह जाँचने के लिए कथन कि क्या उच्च संख्या निम्न संख्या के बराबर या उससे कम है। 
 
 

 यदि यह कथन सत्य का मूल्यांकन करता है, तो हमारी खोज शुरू होती है। अन्यथा, -1 लौटा दिया जाता है, जो हमारे प्रोग्राम को बताता है कि सूची में एक निर्दिष्ट आइटम नहीं मिल सका। 
 
 

 हमारे if . के अंदर कथन, हम जाँचते हैं कि क्या मध्य संख्या का मान उस संख्या के बराबर है जिसके लिए हम खोज कर रहे हैं। अगर ऐसा है, तो हम उस नंबर को अपने मुख्य कार्यक्रम में वापस कर देते हैं। 
 
 

 यदि यह कथन सत्य का मूल्यांकन नहीं करता है, तो हमारा प्रोग्राम यह देखने के लिए जाँच करता है कि क्या मध्य स्थिति में संख्या उस संख्या से कम है जिसके लिए हम खोज कर रहे हैं। अगर ऐसा है, तो searchItems() विधि फिर से चलाई जाएगी, लेकिन इस बार हमारी कम संख्या हमारे मध्य संख्या से एक बड़ी संख्या के बराबर होगी। यह उन वस्तुओं की संख्या को विभाजित करता है जिन्हें हमारी सूची को दो से खोजने की आवश्यकता होती है। 
 
 

 अन्यथा, searchItems() फिर से चलाया जाता है और सबसे बड़ी संख्या का मान मध्य संख्या घटा एक के बराबर कर दिया जाता है। इसका मतलब है कि हम अपनी खोज को केवल अपनी सूची के बाएं आधे हिस्से में ही परिशोधित कर सकते हैं। 
 
 

 हम अपने कोड का परीक्षण करने के लिए उसी मुख्य फ़ंक्शन का उपयोग कर सकते हैं जिसे हमने पहले लिखा था। आइए देखें कि जब हम अपना कोड चलाते हैं तो क्या होता है:
 
7 इंडेक्स पोजीशन 1 पर पाया गया।
 

 हमारा आइटम फिर से मिला! इस बार, हमने एक पुनरावर्ती दृष्टिकोण के बजाय अपना नंबर खोजने के लिए एक पुनरावर्ती दृष्टिकोण का उपयोग किया।
 
जटिलता विश्लेषण
 

 बाइनरी सर्च एल्गोरिथम में ओ (1) की सबसे अच्छी केस जटिलता है। ऐसा तब होता है जब एल्गोरिथम द्वारा तुलना की जाने वाली पहली वस्तु वह है जिसे खोजा जा रहा है।
 

 एक द्विआधारी खोज एल्गोरिथ्म में ओ (लॉग एन) की औसत और सबसे खराब स्थिति जटिलता है। इसका मतलब यह है कि, ज्यादातर मामलों में और सबसे खराब स्थिति में, एल्गोरिथम की गति लॉगरिदमिक रूप से धीमी हो जाती है, यह इस बात पर निर्भर करता है कि सूची को कितने आइटम खोजना है।
 
निष्कर्ष
 

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

 रैखिक खोजों की तुलना में बाइनरी खोज अधिक कुशल हैं। ऐसा इसलिए है क्योंकि हर बार जब कोई खोज की जाती है तो खोजे जाने वाले मानों की संख्या को दो से विभाजित किया जाता है। 
 
 

 अब आप एक विशेषज्ञ प्रोग्रामर की तरह जावा में बाइनरी सर्च को लागू करने के लिए तैयार हैं।