पायथन में बाइनरी सर्च की व्याख्या करें

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

रैखिक खोज की समय जटिलता ओ (एन) है। जबकि द्विआधारी खोज की समय जटिलता ओ (लॉग एन) है। इसलिए, द्विआधारी खोज कुशल और तेज़-खोज एल्गोरिथम है लेकिन इसका उपयोग केवल एक क्रमबद्ध सरणी से खोज के लिए किया जा सकता है।

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

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

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

हम एरे के अंतिम इंडेक्स के बराबर लेफ्ट इंडेक्स 0 और राइट इंडेक्स के साथ सर्च करना शुरू करेंगे। मध्य तत्व सूचकांक (मध्य) की गणना की जाती है जो कि बाएँ और दाएँ सूचकांक के योग को 2 से विभाजित किया जाता है। यदि आवश्यक तत्व मध्य तत्व से कम है, तो दायाँ सूचकांक मध्य -1 में बदल जाता है, जिसका अर्थ है कि अब हम करेंगे केवल सरणी के पहले भाग को देख रहे हैं। इसी तरह, यदि आवश्यक तत्व मध्य तत्व से बड़ा है, तो बाएं सूचकांक को मध्य + 1 में बदल दिया जाता है, जिसका अर्थ है कि अब हम केवल सरणी के दूसरे भाग को देखेंगे। हम चयनित सरणी आधे के लिए उपरोक्त प्रक्रिया को दोहराएंगे।

हमें कैसे पता चलेगा कि ऐरे में एलीमेंट मौजूद नहीं है?

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

उदाहरण

आइए हम निम्नलिखित क्रमबद्ध सरणी लेते हैं और हमें तत्व 6 खोजने की आवश्यकता है।

एल=0 एच=8 मध्य=4

6<10, इसलिए पहला हाफ लें।

एच=मध्य-1

एल=0 एच=3 मध्य=1

6>5, इसलिए दूसरी छमाही चुनें।

एल=मध्य+1

एल=2 एच=3 मध्य=2

6==6, एक तत्व मिला

इसलिए तत्व 6 इंडेक्स 2 पर पाया जाता है।

कार्यान्वयन

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

द्विआधारी खोज के कार्यान्वयन के लिए कोड नीचे दिया गया है।

उदाहरण

def binary_search(arr,x):
   l=0
   r=len(arr)-1
   while(l<=r):
      mid=(l+r)//2
      if(arr[mid]==x):
         return mid
      elif(x<arr[mid]):
         r=mid-1
      elif(x>arr[mid]):
         l=mid+1
   return -1
array=[1,2,3,4,5,6,7,8,9,10]
a=7
print(binary_search(array,a))
b=15
print(binary_search(array,b))

आउटपुट

6
-1

तत्व 7 इंडेक्स 6 पर मौजूद है।

एलिमेंट 15 ऐरे में मौजूद नहीं है, इसलिए -1 प्रिंट होता है।