পাইথনে বাইনারি সার্চ

একটা সর্টেড লিস্টে একটা আইটেম আছে কিনা, তা খুঁজে দেখার জন্য বাইনারি সার্চ ব্যবহার করা হয়। যদি থেকে থাকে, তাহলে ঐ আইটেমের ইনডেক্স রিটার্ণ করে। এর আগে আমরা লিনিয়ার সার্চ সম্পর্কে জেনেছি। বাইনারি সার্চ লিনিয়ার সার্চ থেকে দ্রুত কাজ করে।

যেমন 1, 3, 4, 5 , 7 , 9 , 12 এই লিস্টে 7 বা ধরে নেই x আছে কিনা, তা খুঁজে বের করব।

লিস্টের প্রথম ইনডেক্সকে lo এবং শেষ ইনডেক্সকে hi ধরে দুইটা পয়েন্টার সেট করি।

এরপর লিস্টের মধ্যের ইনডেক্স বের করি এভাবেঃ mid = lo + hi // 2।  এই ক্ষেত্রে mid = (0+6)//2 = 3। মানে উক্ত লিস্টে 3 হচ্ছে মধ্যের ইনডেক্স এবং 5 হচ্ছে এই ইনডেক্সে থাকা আইটেম।

এখন যদি এই mid ইনডেক্সে 7 পেয়ে যাই, তাহলে এই mid ভ্যালুটা রিটার্ণ করবে। মানে mid ইনডেক্সে 7 রয়েছে। যদি না হয়, তাহলে এই মিড পয়েন্টকে ধরে লিস্টকে দুই ভাগ করে নিতে হবে।

ভাগ করার ক্ষেত্রে x যদি মিড থেকে বড় হয় তাহলে লিস্টের ডান পাশের অংশে উপরের স্টেপ গুলো ফলো করবে। আর x যদি মিড থেকে ছোট হয়, তাহলে লিস্টের বাম পাশের অংশে উপরের স্টেপ ফলো করবে।

যদি x মধ্য ইনডেক্সে থাকা আইটেম থেকে ছোট হত, তাহলে hi পয়েন্টারের ভ্যালু পরিবর্তন করতে হত। সেই ক্ষেত্রে নতুন hi পয়েন্টারের ভ্যালু হবে mid -1।

আমাদের ক্ষেত্রে 7 হচ্ছে মধ্য ইনডেক্সে থাকা আইটেম 5 থেকে বড়। তাই সার্চ করবে লিস্টের ডান পাশের অংশে। এই ক্ষেত্রে নতুন lo পয়েন্টারের ভ্যালু হবে mid + 1।

নতুন lo এবং hi এর মাধ্যমে নতুন লিস্টে আবার মধ্য ইনডেক্স খুঁজে বের করবে। এই ক্ষেত্রে হচ্ছে (0+2)//2 = 1। এর মানে হচ্ছে নতুন mid ইনডেক্স হচ্ছে 1 এবং এর ভ্যালু হচ্ছে 9।

এরপর এই ধাপে আবারও দেখবে যে mid ইনডেক্সে থাকা ভ্যালুটি 7 কিনা। যেহেতু mid ইনডেক্সে থাকা সংখ্যাটি 7 নয়, তাই মিড ভ্যালুর সাথে তুলনা করে দেখবে 7 বড় না কি ছোট। এই ক্ষেত্রে দেখবে 7 হচ্ছে 9 থেকে ছোট। তাই এই mid ভ্যালুকে ধরে লিস্টের বামে অংশে সার্চ করবে।

এই ক্ষেত্রে নতুন hi ভ্যালু হবে mid – 1 = 1 – 1 = 0। অর্থাৎ নতুন hi ভ্যালু হচ্ছে লিস্টের প্রথম ইনডেক্স। এই  সময় এসে দেখবে lo এবং hi একই ইনডেক্সে পয়েন্ট করবে। যদি ঐ ইনডেক্সে 7 থাকে, তাহলে আমরা রিটার্ণ করব যে 7 পাওয়া গেছে। যদি না পাওয়া যায়, তাহলে প্রোগ্রাম জানাবে যে সংখ্যাটি লিস্টে পাওয়া যায় নি।

পুরো ধাপ গুলো একটা ইমেজেঃ

উপরের স্টেপ গুলো পাইথনে নিচের মত করে ইমপ্লিমেন্ট করতে পারিঃ

def b_s(lst, x):
    lo = 0
    hi = len(lst) -1

# repeat until lo & hi meet
    while lo <= hi:
      
        mid = (lo + hi) // 2
        if lst[mid] == x:
            return mid
        elif x < lst[mid]:
            hi = mid - 1
        else:
            lo = mid + 1
    return -1


result = b_s([3, 4, 5, 6, 7, 8, 9], 7)

if result != -1:
    print("item is at index: " + str(result))
else:
    print("not found in the list")

উপরের প্রোগ্রামে b_s বা binary_search ফাংশনটি দুইটা প্যারামিটার ইনপুট নিবে। একটা হচ্ছে লিস্ট, আরেকটা হচ্ছে ঐ লিস্টে যে আইটেমটা খুঁজে বের করতে হবে, তা।
যেমন আমরা লিস্ট হিসেবে পাস করেছি [3, 4, 5, 6, 7, 8, 9] এবং যে আইটেম খুঁজে দেখব, তা হিসেবে পাস করেছি 7।

প্রোগ্রামটি রান করলে আউটপুট দিবেঃ

item is at index: 4

এখন 7 এর পরিবর্তে অন্য কোন সংখ্যা যদি পাস করি, যেটা লিস্টে নেই, যেমন 14, তাহলে প্রোগ্রামটি আউটপুট দিতঃ

not found in the list