Binary Search Python: चरण-दर-चरण गाइड

Python बाइनरी सर्च क्रमबद्ध सरणी में किसी आइटम की स्थिति ढूंढता है। यह सूची को आधा में विभाजित करता है। यदि निर्दिष्ट मान मध्य संख्या से अधिक है, तो खोज सूची के दाईं ओर केंद्रित होती है। अन्यथा, खोज सूची के बाईं ओर संख्या ढूंढती है।

आप सूची में किसी आइटम की स्थिति कैसे ढूंढते हैं? बाइनरी सर्च इसमें आपकी मदद करता है। बाइनरी सर्च का उपयोग करके, आप क्रमबद्ध सरणी के अंदर किसी तत्व की स्थिति आसानी से ढूंढ सकते हैं।

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

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

Python Binary Search क्या है?

Python बाइनरी सर्च एक एल्गोरिदम है जो क्रमबद्ध सरणी में किसी तत्व की स्थिति ढूंढता है। बाइनरी सर्च बार-बार सूची को दो हिस्सों में विभाजित करता है। फिर, खोज तुलना करती है कि कोई मान सूची में मध्य मान से अधिक या कम है।

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

पहला दृष्टिकोण जिसका आप उपयोग कर सकते हैं वह पुनरावृत्त विधि (iterative method) है। इस दृष्टिकोण में, स्टेटमेंट्स के सेट को सरणी में किसी तत्व की स्थिति निर्धारित करने के लिए दोहराया जाता है। Python में, हम इस उद्देश्य के लिए while लूप का उपयोग करते हैं।

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

Binary Search Tree Python: चरण-दर-चरण

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

हम अपनी सूची में संख्या "22" खोजने जा रहे हैं।

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

हमारा अगला चरण सरणी में मध्य तत्व ढूंढना है, जो 14 है। यदि यह मान उस मान के बराबर है जिसे हम खोज रहे हैं, तो इस मान को लौटाया जाना चाहिए।

इस मामले में, 14, 22 के समान नहीं है। इसलिए, हमारे प्रोग्राम को तुलना करने की आवश्यकता है।

हम उस संख्या की तुलना करने जा रहे हैं जिसे हम वर्तमान मध्य तत्व के दाईं ओर तत्वों के मध्य तत्व के साथ खोज रहे हैं। हम केवल ऐसा करेंगे यदि हम जिस संख्या को खोज रहे हैं वह मध्य संख्या से अधिक है। अन्यथा, हम वर्तमान मध्य तत्व के बाईं ओर मध्य तत्व के साथ तत्व की तुलना करेंगे।

संख्या 22, 14 से अधिक है। हमारा प्रोग्राम हमारे वर्तमान मध्य तत्व (14) के दाईं ओर मध्य तत्व के साथ 22 की तुलना करना शुरू करता है। इस मामले में, वह संख्या 22 है। यह उस संख्या के बराबर है जिसे हम खोज रहे हैं।

हमें अपना मध्य मान मिल गया। हमारा प्रोग्राम अब उस संख्या की इंडेक्स स्थिति लौटाएगा। इस मामले में, 22 की इंडेक्स स्थिति 3 है (याद रखें, सूचियाँ 0 से अनुक्रमित होती हैं!)।

Python में Binary Search कैसे लागू करें

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

Python में पुनरावृत्त बाइनरी सर्च

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

बाइनरी सर्च फ़ंक्शन

आइए अपने बाइनरी सर्च के लिए Python फ़ंक्शन को परिभाषित करके शुरू करें:

def findValue(numbers, number_to_find):
    low = 0
    high = len(numbers) - 1
    while low <= high:
        middle = low + (high - low) // 2
        if numbers[middle] == number_to_find:
            return middle
        elif numbers[middle] < number_to_find:
            low = middle + 1
        else:
            high = middle - 1
    return -1

हमारा फ़ंक्शन दो पैरामीटर स्वीकार करता है: वह सूची जिसके माध्यम से हम खोजना चाहते हैं, और वह संख्या जिसे हम अपनी सूची में ढूंढना चाहते हैं।

हमने फिर सूची में निम्नतम और उच्चतम मानों के लिए डिफ़ॉल्ट मानों को संग्रहीत करने के लिए दो Python वेरिएबल्स घोषित किए। low 0 पर सेट है, जो सूची में शुरुआती इंडेक्स मान है। high सूची की लंबाई माइनस एक पर सेट है (क्योंकि सूचियाँ शून्य से अनुक्रमित होती हैं)।

हमारा अगला चरण Python व्हाइल लूप घोषित करना था। यह लूप तब चलता है जब निम्नतम तत्व उच्चतम संख्या से छोटा या बराबर होता है। इसका मतलब है कि हमारा लूप केवल तभी चलेगा जब हमारी संख्या अभी तक नहीं मिली है।

फिर, हम मध्य संख्या की गणना करते हैं। हम सबसे कम मान को सबसे अधिक मान से घटाकर ऐसा करते हैं। फिर हम उस संख्या का मॉड्यूलो (शेष) गणना करते हैं जब 2 से विभाजित किया जाता है। फिर, हम मॉड्यूलो को सबसे कम संख्या के मान में जोड़ते हैं।

यदि हमारी सूची में मध्य संख्या उस संख्या के समान है जिसे हम ढूंढना चाहते हैं, तो हम उस संख्या की स्थिति लौटाते हैं।

हम अपनी नई "low" संख्या को मध्य स्थिति से एक अधिक के बराबर सेट करते हैं। यह तब होता है जब मध्य संख्या उस संख्या से कम होती है जिसे हम ढूंढना चाहते हैं। यह हमारी खोज को हमारी सूची के बाईं ओर ले जाता है, जैसे हमने अपने दृश्य उदाहरण में पहले किया था।

अन्यथा, हम अपनी "high" संख्या को मध्य स्थिति से एक कम के बराबर सेट करते हैं। यह हमारी खोज को हमारी सूची के दाईं ओर ले जाता है।

यह तब तक दोहराया जाता है जब तक low high के बराबर या कम नहीं हो जाता। यदि हमारा मान नहीं मिलता है, तो हम -1 लौटाते हैं। हम एक मिनट में बात करेंगे कि क्यों।

खोज निष्पादित करें

findValue फ़ंक्शन के बाहर अपने प्रोग्राम के नीचे निम्न कोड जोड़ें:

numbers = [7, 9, 14, 22, 34]
number_to_find = 22
final = findValue(numbers, number_to_find)
if final == -1:
    print("This item was not found in the list.")
else:
    print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")

हमने उन आइटम्स की सूची घोषित करके शुरू किया है जिनके माध्यम से हम खोजना चाहते हैं। फिर हमने वह संख्या निर्दिष्ट की जिसे हम ढूंढना चाहते हैं, जो 22 है।

अगला, हम अपने findValue() फ़ंक्शन को कॉल करते हैं और उसके माध्यम से सूची पास करते हैं।

यहाँ वह -1 आता है जिसकी हमने पहले चर्चा की थी। यदि हमारे फ़ंक्शन द्वारा लौटाई गई संख्या -1 है, तो इसका मतलब है कि हमारा आइटम सूची में नहीं मिला। प्रोग्रामर्स अक्सर ऐसी स्थितियों में -1 का उपयोग करते हैं क्योंकि हमारा खोज फ़ंक्शन ऋणात्मक संख्या नहीं लौटा सकता।

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

हमारा कोड लौटाता है:

The number 22 was found at index position 3.

अब हम जानते हैं कि संख्या 22 इंडेक्स स्थिति 3 पर दिखाई देती है।

Python में पुनरावर्ती बाइनरी सर्च

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

पुनरावर्ती फ़ंक्शन परिभाषित करें

हमारे पिछले उदाहरण की तरह, हम बाइनरी सर्च करने वाले फ़ंक्शन को लिखकर शुरू करेंगे:

def findValue(numbers, number_to_find, low, high):
    if high >= low:
        middle = low + (high - low) // 2
        if numbers[middle] == number_to_find:
            return middle
        elif numbers[middle] < number_to_find:
            return findValue(numbers, number_to_find, middle + 1, high)
        else:
            return findValue(numbers, number_to_find, low, middle - 1)
    else:
        return -1

हमारा कोड हमारे पिछले उदाहरण से कुछ हद तक समान है।

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

हम पिछले उदाहरण के समान दृष्टिकोण का उपयोग करके मध्य संख्या की गणना करते हैं। पहले, हम निम्नतम को उच्चतम से घटाते हैं। फिर, हम उस मान का मॉड्यूलो (शेष) गणना करते हैं जब 2 से विभाजित किया जाता है। अंत में, हम निम्नतम संख्या जोड़ते हैं।

फिर हमने एक if स्टेटमेंट लिखा है जो तय करता है कि हमारा बाइनरी सर्च कैसे आगे बढ़ना चाहिए:

• यदि मध्य संख्या उस संख्या के बराबर है जिसे हम ढूंढ रहे हैं, तो उस संख्या की स्थिति लौटाई जाती है।
• यदि मध्य संख्या उस संख्या से कम है जिसे हम ढूंढ रहे हैं, तो हमारा findValue() फ़ंक्शन फिर से कॉल किया जाता है। इस बार, low का मान हमारे मध्य मान से एक अधिक के बराबर सेट किया जाता है।
• यदि मध्य संख्या उस संख्या से अधिक है जिसे हम ढूंढ रहे हैं, तो findValue() फ़ंक्शन कॉल किया जाता है। "high" का मान मध्य मान से एक कम के बराबर होगा।

मुख्य प्रोग्राम लिखें

हमारे पास बस अपना मुख्य प्रोग्राम लिखना बाकी है:

numbers = [7, 9, 14, 22, 34]
number_to_find = 22
final = findValue(numbers, number_to_find, 0, len(numbers) - 1)
if final == -1:
    print("This item was not found in the list.")
else:
    print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")

हमारा मुख्य प्रोग्राम हमारे पहले उदाहरण के समान है सिवाय एक अंतर के। हम अपने findValue() फ़ंक्शन में दो नए पैरामीटर्स पास कर रहे हैं: low और high।

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

हमारा कोड लौटाता है:

The number 22 was found at index position 3.

हमें पहले वाले के समान परिणाम मिला है। इस उदाहरण में, हमने अपने बाइनरी सर्च को करने के लिए पुनरावृत्त प्रोग्राम के बजाय पुनरावर्ती प्रोग्राम का उपयोग किया है।

Python Binary Search कब उपयोग करना चाहिए?

बाइनरी सर्च संख्याओं की सूची के माध्यम से खोज करने का एक कुशल तरीका है। यह खोज रैखिक खोज (linear search) से अधिक कुशल है। ऐसा इसलिए है क्योंकि बाइनरी विधि क्रमबद्ध सूची के मध्य को ढूंढते ही आपकी खोज को आधा कर देती है।

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

Python में Binary Search जटिलता विश्लेषण

बाइनरी सर्च की जटिलता क्या है? यह एक अच्छा सवाल है।

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

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

निष्कर्ष

बाइनरी सर्च सूची में मान की इंडेक्स स्थिति ढूंढने का एक कुशल तरीका है।

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

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

Python के बारे में अधिक जानने के लिए, हमारा How to Learn Python गाइड पढ़ें।