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

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

परिचय

एक प्रोग्रामर के रूप में, आप किसी समस्या का सबसे अच्छा समाधान खोजना चाहते हैं ताकि आपका कोड ना केवल सही हो बल्कि एक कुशल कोड भी हो। यह सब-ऑप्टिमल एल्गोरिदम चुनने का मतलब एक लंबे समय में पूरा होना, कोड की बढ़ी हुई जटिलता या इससे भी बुरा प्रोग्राम हो सकता है जो की क्रैश हो जाता है। लेकिन डाटा के कलेक्शन में आइटम्स का पता लगाने के लिए एक सर्च एल्गोरिदम का उपयोग किया जा सकता है। किसी array में आइटम को सर्च करने के लिए जावास्क्रिप्ट लैंग्वेज में कई मेथड है जैसे कि find। हालांकि, यह मेथड लिनियर सर्च का उपयोग करते हैं। एक लिनियर सर्च एल्गोरिदम एक लिस्ट की शुरुआत से शुरू होता है और प्रत्येक एलिमेंट की सर्च वैल्यू के साथ तुलना करता है जब तक की उसे यह नहीं मिलती है। यह ठीक है जब आपके पास एलिमेंट की एक छोटी संख्या होती है। लेकिन जब आप बड़ी लिस्ट सर्च कर रहे होते हैं, जिसमें हजारों या लाखों एलिमेंट्स होते हैं, तो आपको आइटम्स का पता लगाने के लिए एक बेहतर तरीका चाहिए। यह वह मौका है है जब आप बाइनरी सर्च का उपयोग करेंगे। इस ट्यूटोरियल में, मैं बताऊंगा कि बाइनरी सर्च कैसे काम करता है और जावास्क्रिप्ट में एल्गोरिदम को कैसे अप्लाई किया जाता है। सबसे पहले, हम लिनियर सर्च एल्गोरिदम का रिव्यू करेंगे।

लिनियर सर्च

हम जावास्क्रिप्ट में लिनियर सर्च को अप्लाई करने के तरीके के बारे में बताकर शुरू करते हैं। हम linearSearch नामक एक फंक्शन बनाएंगे जो वैल्यू को इन्टिजर या स्ट्रिंग और पैरामीटर के रूप में एक array को स्वीकार करता है। फंक्शन वैल्यू के लिए array में प्रत्येक एलिमेंट को सर्च करेगा और यदि यह मिल जाता है तो array में वैल्यू की पोजीशन रिटर्न कर देगा। यदि वैल्यू array में नहीं है, तो यह -1 रिटर्न करेगा। उदाहरण के लिए, linearSearch(1, [3, 4, 2, 1, 5]) को कॉल करके 3 रिटर्न आएगा और linearSearch(0, [3, 4, 2, 1, 5]) को कॉल करके -1 रिटर्न होगा।

यहाँ हमारे फंक्शन के लिए कुछ सुडोकोड है

Set found to false
Set position to −1
Set index to 0
while found is false and index < number of elements
    if list[index] is equal to search value
        Set found to true
        Set position to index
    else Add 1 to index
return position

लिनियर सर्च का जावास्क्रिप्ट इंप्लीमेंटेशन

यहां लिनियर सर्च एल्गोरिदम का जावास्क्रिप्ट इंप्लीमेंटेशन है

function linearSearch(value, list) {
    let found = false;
    let position = -1;
    let index = 0;

    while(!found && index < list.length) {
        if(list[index] == value) {
            found = true;
            position = index;
        } else {
            index += 1;
        }
    }
    return position;
}

यह ध्यान रखना महत्वपूर्ण है कि लिनियर सर्च एल्गोरिदम को सॉर्टेड लिस्ट का उपयोग करने की आवश्यकता नहीं है। इसके अलावा, एल्गोरिदम को अलग-अलग सिनेरियो में उपयोग के लिए कस्टमाइज किया जा सकता है जैसे कि key द्वारा ऑब्जेक्ट्स का एक array में सर्च करना। यदि आपके पास क्लाइंट डाटा का एक array है जिसमें पहले और आखिरी नाम की keys शामिल है, तो आप यह टेस्ट कर सकते हैं कि क्या array में पहले स्पेसिफाई नाम वाला क्लाइंट है या नहीं। उस स्थिति में, चेक करने की बजाय की यदि list[index] हमारे सर्च वैल्यू के बराबर है तो आप list[index].first को चेक करेंगे।

ऊपर के उदाहरण में, मैंने 5 एलिमेंट्स के साथ एक array पर linearSearch फंक्शन का उपयोग किया। सबसे खराब स्थिति में, जब सर्च वैल्यू लिस्ट में नहीं है या लिस्ट के अंत में है, तो फंक्शन को 5 कंपैरिजन करने होंगे। क्योंकि हमारा array इतना छोटा है कि एक अलग एल्गोरिदम का उपयोग करके कस्टमाइज करने की कोई आवश्यकता नहीं है। हालांकि, एक निश्चित पॉइंट तक, यह लिनियर सर्च एल्गोरिदम का उपयोग करने के लिए अब एफिशिएंट नहीं है और यह वह मौका है जब बायनरी सर्च एल्गोरिथम का उपयोग करना बेहतर होगा।

बाइनरी सर्च

कल्पना करें कि आप एक नंबर अनुमान लगाने का खेल खेल रहे हैं। आप को 1 और 100 के बीच की संख्या का अनुमान लगाने के लिए कहा जाता है। यदि आप की संख्या बहुत बड़ी है या बहुत छोटी है, तो आपको हिंट मिलेगा। आपकी स्ट्रेटजी क्या होगी? क्या आप बेहतरीन ढंग से संख्याएं चुनेंगे? क्या 1 से शुरू करेंगे, फिर 2 से, और जब तक आप सही अनुमान नहीं लगाते हैं? यहां तक कि अगर आपके पास असीमित अनुमान हो, तब भी आप यथासंभव कम समय में ही सही अनुमान लगाना चाहेंगे। इसलिए, आप अनुमान लगाने की शुरुआत 50 से कर सकते हैं। यदि संख्या अधिक है तो आप 75 का अनुमान लगा सकते हैं। यदि कम है तो इसका मतलब है कि संख्या 50 और 75 के बीच है और आप एक संख्या चुनेंगे जो बीच में है। जब तक आप सही संख्या को नहीं खोज लेते, आप इसी तरह से चलते जाएंगे। यह बायनरी खोज कैसे काम करता है, उसी के समान है।

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

लिस्ट में 9 को सर्च करने के लिए:

1 2 3 4 5 6 7 8 9 10

हम पहले मेडल एलिमेंट को फाइंड करते हैं। यह Math.floor((first + last)/2) पोजीशन में वह एलिमेंट है जहां first पहला इंडेक्स है, और last अंतिम इंडेक्स है। हम राउंड डाउन करना चाहते हैं ताकि इस मामले में रिजल्ट एक फ्रेक्शन (fraction) हो, यह होल (whole) नंबर बन जाए। इस लिस्ट का मिडिल एलिमेंट 5 है। हमारी सर्च वैल्यू 9 है जो 5 से अधिक है, इसलिए हम लिस्ट में सर्च करते हैं।

6 7 8 9 10

इस हिस्से का मिडल एलिमेंट 8 है। नौ 8 से बड़ा होता है इसलिए हम लिस्ट में आगे सर्च करेंगे।

9 10

मिडल एलिमेंट 9 है, तो हम यहां अपने सर्च को रोक सकते हैं।

यहां कुछ सूडोकोड है जो बाइनरी सर्च की ऊपर दी गई एल्गोरिदम को एक्सप्रेस करते हैं:

Set first to 0
Set last to the last index in the list
Set found to false
Set position to −1
while found is false and first is less than or equal to last
    Set middle to the index halfway between first and last
    if list[middle] equals the desired value
        Set found to true
        Set position to middle
    else if list[middle] is greater than the desired value
        Set last to middle − 1
    else
        Set first to middle + 1
return position

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

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

हम एक फंक्शन बनाएंगे, binarySearch, जो वैल्यू और एक array को पैरामीटर्स के रूप में स्वीकार करता है। यह इंडेक्स को रिटर्न करेगा जहां वैल्यू लिस्ट में पाई जाती है। यदि वैल्यू नहीं पाई जाती है तो यह -1 रिटर्न करेगा। यह हमारे जावास्क्रिप्ट में लिखा गया इंप्लीमेंटेशन है:

function binarySearch(value, list) {
    let first = 0;    //left endpoint
    let last = list.length - 1;   //right endpoint
    let position = -1;
    let found = false;
    let middle;

    while (found === false && first <= last) {
        middle = Math.floor((first + last)/2);
        if (list[middle] == value) {
            found = true;
            position = middle;
        } else if (list[middle] > value) {  //if in lower half
            last = middle - 1;
        } else {  //in in upper half
            first = middle + 1;
        }
    }
    return position;
}

निष्कर्ष

इस ट्यूटोरियल में, हमने देखा कि लिनियर सर्च और बाइनरी सर्च एल्गोरिदम को कैसे इंप्लीमेंट किया जाए। लिनियर सर्च एल्गोरिदम आसान है और इसके लिए एक सॉर्टेड array की आवश्यकता नहीं है। हालांकि, बड़े arrays के साथ उपयोग करना इनएफिशिएंट है। सबसे खराब स्थिति में, एल्गोरिदम को n कंपैरिजन करने वाले सभी एलिमेंट्स को सर्च करना होगा (जहां n एलिमेंट्स की संख्या है)।

दूसरी ओर, बाइनरी सर्च एल्गोरिथम, आपको पहले array को सॉर्टेड करने की आवश्यकता है और इसे इंप्लीमेंट करना अधिक मुश्किल है। हालांकि, यह सॉर्टिंग की कॉस्ट के बारे में विचार करने पर भी यह अधिक एफिशिएंट है। उदाहरण के लिए, 10 एलिमेंट्स के साथ एक array ज्यादा से ज्यादा 4 कंपैरिजन करेगा अगर हम बाइनरी सर्च से करते हैं इसके मुकाबले लिनियर सर्च 10 बार करेगा-- बहुत बड़ा इंप्रूवमेंट नहीं है। हालांकि 1,000,000 एलिमेंट्स के साथ बाइनरी सर्च में सबसे खराब स्थिति केवल 20 कंपैरिजंस की है। यह लिनियर सर्च के मुकाबले बहुत ही बड़ा इंप्रूवमेंट है!

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