পাইথন প্রোগ্রাম: বাইনারি সার্চ অ্যালগরিদম

এই নিবন্ধে আমরা একটি সর্ট করা লিস্টে একটি উপাদান খুঁজে বের করার জন্য বাইনারি সার্চের সমাধান এবং পদ্ধতি নিয়ে আলোচনা করব।

সমস্যা বিবরণ - আমাদের একটি সর্ট করা লিস্ট দেওয়া থাকবে এবং বাইনারি সার্চের সাহায্যে একটি উপাদান খুঁজে বের করতে হবে।

অ্যালগরিদম

• x কে মাঝপথের উপাদানের সাথে তুলনা করুন।

• যদি x মাঝপথের উপাদানের সাথে মিলে যায়, তবে মাঝপথের ইনডেক্স ফেরত দিন।

• অন্যথায় যদি x মাঝপথের উপাদানের চেয়ে বড় হয়, তবে x শুধু মাঝপথের উপাদানের পরে ডান পাশের সাবঅ্যারেতে থাকতে পারে। তাই ডান পাশের জন্য পুনরাবৃত্তি করুন।

• অন্যথায় (x ছোট হলে) বাম পাশের জন্য পুনরাবৃত্তি করুন।

রিকারসিভ অ্যালগরিদম

উদাহরণ

def binarySearchAppr(arr, start, end, x):
    # শর্ত যাচাই
    if end >= start:
        mid = start + (end - start) // 2
        # যদি উপাদান মাঝপথে থাকে
        if arr[mid] == x:
            return mid
        # যদি উপাদান মাঝপথের চেয়ে ছোট হয়
        elif arr[mid] > x:
            return binarySearchAppr(arr, start, mid-1, x)
        # অন্যথায় উপাদান মাঝপথের চেয়ে বড়
        else:
            return binarySearchAppr(arr, mid+1, end, x)
    else:
        # উপাদান অ্যারেতে পাওয়া যায়নি
        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):
    # শর্ত যাচাই
    if end >= start:
        mid = start + (end - start) // 2
        # যদি উপাদান মাঝপথে থাকে
        if arr[mid] == x:
            return mid
        # যদি উপাদান মাঝপথের চেয়ে ছোট হয়
        elif arr[mid] > x:
            return binarySearchAppr(arr, start, mid-1, x)
        # অন্যথায় উপাদান মাঝপথের চেয়ে বড়
        else:
            return binarySearchAppr(arr, mid+1, end, x)
    else:
        # উপাদান অ্যারেতে পাওয়া যায়নি
        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

উপসংহার

এই নিবন্ধে আমরা বাইনারি সার্চ প্রয়োগ করার পদ্ধতি শিখেছি।