पायथन में बाइनरी सर्च (द्विभाजित)

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

हम पायथन में द्विभाजित का उपयोग करते हुए तीन अलग-अलग कार्य देखेंगे।

किसी तत्व की पहली घटना का पता लगाना

bisect.bisect_left(a, x, lo =0, hi =len(a)) इस फ़ंक्शन का उपयोग क्रमबद्ध सूची में x के सबसे बाएं सम्मिलन बिंदु को वापस करने के लिए किया जाता है। इस मामले में अंतिम दो पैरामीटर वैकल्पिक हैं। इन दोनों का इस्तेमाल सबलिस्ट में सर्च करने के लिए किया जाता है।

उदाहरण

from bisect import bisect_left
def BinSearch(a, x):
   i = bisect_left(a, x)
   if i != len(a) and a[i] == x:
      return i
   else:
      return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(4)
pos = BinSearch(a, x)
if pos == -1:
   print(x, "is absent")
else:
   print("First occurrence of", x, "is at position", pos)

आउटपुट

First occurrence of 4 is at position 2

x से छोटा सबसे बड़ा मान ढूँढना

bisect_left विकल्प का उपयोग करके, हम बड़ा मान प्राप्त कर सकते हैं, जो x (कुंजी) से छोटा है।

उदाहरण

from bisect import bisect_left
def BinSearch(a, x):
   i = bisect_left(a, x)
   if i :
      return i-1
   else:
      return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(8)
pos = BinSearch(a, x)
if pos == -1:
   print(x, "is absent")
else:
   print("Larger value, smaller than", x, "is at position", pos)

आउटपुट

Larger value, smaller than 8 is at position 4

x की सबसे सही आवृत्ति का पता लगाना

bisect.bisect_right(a, x, lo =0, hi =len(a)) इस फ़ंक्शन का उपयोग क्रमबद्ध सूची में x के सबसे सही सम्मिलन बिंदु को वापस करने के लिए किया जाता है। इस मामले में अंतिम दो पैरामीटर वैकल्पिक हैं। इन दोनों का इस्तेमाल सबलिस्ट में सर्च करने के लिए किया जाता है।

उदाहरण

from bisect import bisect_right
def BinSearch(a, x):
   i = bisect_right(a, x)
   if i != len(a) + 1 and a[i-1] == x:
      return i-1
   else:
      return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(36)
pos = BinSearch(a, x)
if pos == -1:
   print(x, "is absent")
else:
   print("Right most occurrence of", x, "is at position", pos)

आउटपुट

Right most occurrence of 36 is at position 9