এই প্রবন্ধে, আমরা প্রদত্ত সমস্যার বিবৃতিটি সমাধান করার জন্য সমাধান এবং পদ্ধতি সম্পর্কে শিখব।
সমস্যা বিবৃতি - আমাদের একটি সাজানো তালিকা দেওয়া হবে এবং আমাদের একটি বাইনারি অনুসন্ধানের সাহায্যে একটি উপাদান খুঁজে বের করতে হবে৷
অ্যালগরিদম
-
মধ্যম উপাদানের সাথে 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
উপসংহার
এই নিবন্ধে, আমরা বাইনারি অনুসন্ধান প্রয়োগ করার পদ্ধতি সম্পর্কে শিখেছি।
