इस लेख में, हम दिए गए समस्या कथन को हल करने के लिए समाधान और दृष्टिकोण के बारे में जानेंगे।
समस्या कथन − हमें एक क्रमबद्ध सूची दी जाएगी और हमें एक द्विआधारी खोज की मदद से एक तत्व खोजने की जरूरत है।
एल्गोरिदम
-
x की तुलना मध्य तत्व से करें।
-
यदि x मध्य तत्व से मेल खाता है, तो हम मध्य सूचकांक लौटाते हैं।
-
अन्यथा यदि x मध्य तत्व से बड़ा है, तो x मध्य तत्व के बाद केवल दाहिने आधे उप-सरणी में स्थित हो सकता है। इसलिए हम दाहिने आधे भाग की पुनरावृत्ति करते हैं।
-
अन्यथा (x छोटा है) बाएं आधे हिस्से के लिए पुनरावृत्ति करें
पुनरावर्ती एल्गोरिदम
उदाहरण
def binarySearchAppr (arr, start, end, x):
# check condition
if end >= start:
mid = start + (end- start)//2
# If element is present at the middle
if arr[mid] == x:
return mid
# If element is smaller than mid
elif arr[mid] > x:
return binarySearchAppr(arr, start, mid-1, x)
# Else the element greator than mid
else:
return binarySearchAppr(arr, mid+1, end, x)
else:
# Element is not found in the array
return -1
arr = sorted(['t','u','t','o','r','i','a','l'])
x ='r'
result = binarySearchAppr(arr, 0, len(arr)-1, x)
if result != -1:
print ("Element is present at index "+str(result))
else:
print ("Element is not present in array") इटरेटिव एल्गोरिथम
उदाहरण
def binarySearchAppr (arr, start, end, x):
# check condition
if end >= start:
mid = start + (end- start)//2
# If element is present at the middle
if arr[mid] == x:
return mid
# If element is smaller than mid
elif arr[mid] > x:
return binarySearchAppr(arr, start, mid-1, x)
# Else the element greator than mid
else:
return binarySearchAppr(arr, mid+1, end, x)
else:
# Element is not found in the array
return -1
arr = sorted(['t','u','t','o','r','i','a','l'])
x ='r'
result = binarySearchAppr(arr, 0, len(arr)-1, x)
if result != -1:
print ("Element is present at index "+str(result))
else:
print ("Element is not present in array") Element is present at index 4
निष्कर्ष
इस लेख में, हमने बाइनरी सर्च को लागू करने के तरीके के बारे में सीखा।