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

जावास्क्रिप्ट में बाइनरी सर्च कैसे कोड करें

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

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

इस गाइड में, हम बात करेंगे कि बाइनरी सर्च क्या हैं और वे कैसे काम करते हैं। फिर हम दो अलग-अलग दृष्टिकोणों का उपयोग करके बाइनरी सर्च को लागू करेंगे: इटरेटिव और रिकर्सिव।

आइए जावास्क्रिप्ट में बाइनरी सर्च एल्गोरिदम बनाएं!

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

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

यह ऐरे के बीच में शुरू होता है और जांचता है कि मध्य आइटम उस संख्या से कम, बराबर, या अधिक है या नहीं जिसे आप खोज रहे हैं।

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

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

बाइनरी सर्च का उपयोग कैसे करें

बाइनरी सर्च समझना आसान है एक बार जब आप इसकी आदत डाल लेते हैं।

इससे पहले कि हम बाइनरी सर्च एल्गोरिदम को लागू करें, आइए एक चरण-दर-चरण चलते हैं। हम सूची में संख्या "9" ढूंढने जा रहे हैं। आइए सॉर्टेड सूची से शुरू करें:

पहले, हमें मध्य संख्या ढूंढनी होगी और इसे वेरिएबल को असाइन करना होगा। यह पहली और अंतिम संख्या का योग निकालकर और इसे दो से विभाजित करके पाया जाता है। हम इस वेरिएबल को "middle" कहेंगे:

8 हमारी मध्य संख्या है। फिर, हम मध्य संख्या की तुलना उस संख्या से कर सकते हैं जिसे हम खोज रहे हैं। यदि मध्य संख्या उस संख्या के बराबर है जिसे हम खोज रहे हैं, तो हमारी खोज रुक सकती है।

इस उदाहरण में, 8, 9 के बराबर नहीं है। हमारी खोज जारी रहती है।

अगला, हमें तुलना करने की आवश्यकता है कि क्या मध्य संख्या 9 से अधिक है। यह नहीं है।

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

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

बाइनरी सर्च सूची के ऊपरी आधे हिस्से पर फिर से दोहराता है क्योंकि 9, 8 से अधिक है:

हम फिर से मध्य संख्या ढूंढते हैं। यह 9 है। हम 9 की तुलना उस संख्या से कर सकते हैं जिसे हम खोज रहे हैं। 9 उस संख्या के बराबर है जिसे हम खोज रहे हैं।

इसका मतलब है कि हमारी खोज रुक सकती है। हमने अपनी सूची में संख्या 9 को सफलतापूर्वक ढूंढ लिया है!

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

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

इटरेटिव बाइनरी सर्च

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

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

function binarySearch(array, numberToFind) { let start = 0; let end = array.length - 1; while (start <= end) { let middle = Math.floor((start + end) / 2); if (array[middle] === numberToFind) { return middle; } else if (array[middle] < numberToFind) { start = middle + 1; } else { end = middle - 1; } } return -1; }

हम दो वेरिएबल्स को परिभाषित करके शुरू करते हैं: start और end। ये उन उच्चतम और निम्नतम मानों को ट्रैक करते हैं जिनके साथ हमारी खोज काम कर रही है। हम while लूप का उपयोग करते हैं जो तब तक चलता है जब तक शुरुआती संख्या अंतिम संख्या से अधिक नहीं हो जाती। यह लूप सूची में शुरुआत और अंत के बीच मध्य संख्या की गणना करता है।

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

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

हमारा फंक्शन अभी काम नहीं करता। हमें मुख्य प्रोग्राम लिखने की आवश्यकता है जो इसे कॉल करता है:

let numbers = [2, 6, 8, 9, 10]; let toFind = 9; let findNumber = binarySearch(numbers, toFind); if (findNumber !== -1) { console.log(`${toFind} has been found at position ${findNumber}.`); } else { console.log(`${toFind} has not been found.`); }

हमने खोज करने के लिए संख्याओं की सूची और वह संख्या जिसे हम अपनी सूची में ढूंढना चाहते हैं, परिभाषित की है। अगला, हमने binarySearch फंक्शन को कॉल किया है। यह हमारी खोज करेगा। खोज या तो -1 या उस आइटम की स्थिति लौटाएगी जिसे हम खोज रहे हैं।

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

आइए अपना कोड चलाएं:

9 has been found at position 3.

यह हमें बताता है कि हमारी खोज सफल रही!

रिकर्सिव बाइनरी सर्च

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

नई जावास्क्रिप्ट फाइल खोलें और यह कोड पेस्ट करें:

function binarySearch(array, numberToFind, start, end) { if (start => end) { return -1; } let middle = Math.floor((start + end) / 2); if (array[middle] === numberToFind) { return middle; } else if (array[middle] < numberToFind) { return binarySearch(array, numberToFind, middle + 1, end); } else { return binarySearch(array, numberToFind, start, middle - 1); } }

यह कोड हमारी पहली खोज के समान तुलनाएं करता है। यह जांचता है कि मध्य संख्या उस संख्या के बराबर, अधिक, या कम है जिसे हम खोज रहे हैं।

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

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

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

let numbers = [2, 6, 8, 9, 10]; let toFind = 9; let findNumber = binarySearch(numbers, toFind, 0, numbers.length - 1); … 

हमें दो अतिरिक्त पैरामीटर्स पास करने की आवश्यकता है: "start" और "end" के मान। "start" का मान 0 के बराबर है। "end" का मान सूची की लंबाई माइनस वन के बराबर है।

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

9 has been found at position 3.

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

निष्कर्ष

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

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