बाइनरी सर्च पायथन:एक चरण-दर-चरण मार्गदर्शिका

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

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

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

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

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

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

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

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

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

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

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

बाइनरी सर्च ट्री पायथन:चरण-दर-चरण

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

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

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

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

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

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

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

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

पायथन में बाइनरी सर्च कैसे लागू करें

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

पायथन में पुनरावृत्त बाइनरी खोज

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

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

आइए अपनी बाइनरी खोज के लिए पायथन फ़ंक्शन को परिभाषित करके शुरू करें:

def findValue(numbers, number_to_find):
	low = 0
	high = len(listnumbers - 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

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

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

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

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

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

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

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

यह तब तक दोहराया जाता है जब तक कि निम्न उच्च के बराबर या उससे कम न हो। यदि हमारा मान नहीं मिलता है, तो हम -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 पर दिखाई देता है।

पायथन में पुनरावर्ती बाइनरी खोज

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

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

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

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() फ़ंक्शन को फिर से कहा जाता है। इस बार, निम्न . का मान हमारे मध्य मान से एक बड़े मान के बराबर होना तय है।
• अगर बीच की संख्या हमारे द्वारा खोजी जा रही संख्या से बड़ी है, तो findValue() समारोह कहा जाता है। "उच्च" का मान मध्य मान से एक कम के बराबर होगा।

मुख्य कार्यक्रम लिखें

हमें केवल अपना मुख्य कार्यक्रम लिखना है:

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() . में दो नए पैरामीटर दे रहे हैं समारोह:निम्न और उच्च।

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

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

The number 22 was found at index position 3.

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

आपको पायथन बाइनरी सर्च का उपयोग कब करना चाहिए?

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

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

पायथन कॉम्प्लेक्सिटी ब्रेकडाउन में बाइनरी सर्च

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

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

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

निष्कर्ष

किसी सूची में किसी मान की अनुक्रमणिका स्थिति खोजने के लिए बाइनरी खोज एक प्रभावी तरीका है।

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

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

पायथन के बारे में अधिक जानने के लिए, हमारी हाउ टू लर्न पायथन गाइड पढ़ें।