Java में बाइनरी सर्च: एक गाइड

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

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

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

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

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

एक बाइनरी सर्च एक सर्च एल्गोरिदम है जो सॉर्टेड array में किसी तत्व की स्थिति का पता लगाता है।

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

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

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

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

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

बाइनरी सर्च को दो तरीकों से इम्प्लीमेंट किया जा सकता है: इटरेटिवली या रिकर्सिवली।

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

आप हमारे Java रिकर्सन गाइड को पढ़कर रिकर्सन के बारे में अधिक जान सकते हैं।

बाइनरी सर्च को इम्प्लीमेंट करने के लिए सामान्य एल्गोरिदम वही रहता है चाहे आप किसी भी दृष्टिकोण का उपयोग करने का निर्णय लें।

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

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

अगला, हमें अपने array में मध्य तत्व ढूंढना होगा। हम फॉर्मूला का उपयोग करके ऐसा कर सकते हैं: (low + high) / 2। इस मामले में, मध्य तत्व 8 है।

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

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

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

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

Java बाइनरी सर्च कैसे इम्प्लीमेंट करें

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

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

इटरेटिव मेथड

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

class BinarySearch { int searchItems(int array[], int searchingFor, int low, int high) { while (low <= high) { int middle = low + (high - low) / 2; if (array[middle] == searchingFor) { return middle; } else if (array[middle] < searchingFor) { low = middle + 1; } else { high = middle - 1; } } return -1; } }

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

हमारा फंक्शन चार पैरामीटर्स स्वीकार करता है: वह सूची जिसके माध्यम से हम खोजना चाहते हैं (array), वह आइटम जिसे हम खोज रहे हैं (searchingFor), कम नंबर (low), और उच्च नंबर (high)।

हमारे फंक्शन के अंदर हमने एक while लूप घोषित किया है। जब तक "low" का मान "high" से कम या बराबर है, लूप एक्जीक्यूट होगा।

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

यदि वे संख्याएं बराबर हैं, तो वह मान हमारे मेन प्रोग्राम को लौटाया जाता है। यदि नहीं, तो हमारा प्रोग्राम जांचता है कि मध्य पोजीशन पर मान उस मान से कम है या नहीं जिसे हम खोज रहे हैं। यदि यह है, तो एक नया low मान सेट किया जाता है।

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

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

हमारा कोड अभी कुछ नहीं करता क्योंकि हमने अपना मेन प्रोग्राम नहीं लिखा है। अपने BinarySearch क्लास में searchItems() फंक्शन के नीचे निम्न कोड जोड़ें:

public static void main(String args[]) { BinarySearch newSearch = new BinarySearch(); int listToSearch[] = { 6, 7, 8, 9, 10 }; int listLength = listToSearch.length; int numberToFind = 7; int findNumber = newSearch.searchItems(listToSearch, numberToFind, 0, listLength - 1); if (findNumber != -1) { System.out.println(numberToFind + " was found at index position " + findNumber + "."); } else { System.out.println(numberToFind + " was not found in the list."); } }

आइए अपना कोड चलाएं और देखें क्या होता है:

7 was found at index position 1. We've found the position of our number!

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

• listToSearch: वह सूची जिसके माध्यम से हम खोजना चाहते हैं।
• listLength: सूची की लंबाई।
• numberToFind: वह नंबर जिसे हम सूची में खोज रहे हैं।

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

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

रिकर्सिव मेथड

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

आइए एक फंक्शन परिभाषित करके शुरू करें जो हमारे बाइनरी सर्च को रिकर्सिवली परफॉर्म करता है:

class BinarySearch { int searchItems(int array[], int searchingFor, int low, int high) { if (high >= low) { int middle = low + (high - low) / 2; if (array[middle] == searchingFor) { return middle; } else if (array[middle] < searchingFor) { searchItems(array, searchingFor, middle + 1, high); } else { searchItems(array, searchingFor, low, middle - 1); } } return -1; } }

यह फंक्शन हमारे बाइनरी सर्च को एक अलग तरीके से इम्प्लीमेंट करता है। while लूप का उपयोग करने के बजाय, हम एक if स्टेटमेंट का उपयोग यह जांचने के लिए करते हैं कि उच्च नंबर कम नंबर के बराबर या कम है या नहीं।

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

हमारे if स्टेटमेंट के अंदर, हम जांचते हैं कि मध्य नंबर का मान उस मान के बराबर है या नहीं जिसे हम खोज रहे हैं। यदि यह है, तो हम उस नंबर को अपने मेन प्रोग्राम को लौटाते हैं।

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

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

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

7 was found at index position 1.

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

जटिलता विश्लेषण

बाइनरी सर्च एल्गोरिदम की बेस्ट केस जटिलता O(1) है। यह तब होता है जब एल्गोरिदम द्वारा तुलना किया गया पहला आइटम वही होता है जिसे खोजा जा रहा है।

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

निष्कर्ष

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

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

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