বাইনারি সার্চ – ১

তুমি নিশ্চয়ই লক্ষ্য করেছো, ডিকশনারিতে লাখ লাখ শব্দ থাকলেও প্রয়োজনীয় শব্দটা খুঁজে পেতে কখনো খুব বেশি সময় লাগে না। এটার কারণ হলো শব্দগুলো অক্ষর অনুযায়ী সাজানো থাকে (Sorted)। তাই তুমি যদি dynamite শব্দটা ডিকশনারিতে খোজার চেষ্টা করো এবং এলোমেলোভাবে কোনো একটা পাতা খুলে kite শব্দটা খুঁজে পাও, তাহলে তুমি নিশ্চিত হয়ে যেতে পারো যে, তুমি যে শব্দটা খোজার চেষ্টা করছো সেটা বাম দিকে কোথাও আছে। আবার যদি তুমি dear শব্দটা খুঁজে পাও তখন তুমি আর বাম দিকের পাতাগুলোয় খোজার চেষ্টা করবে না। ডান দিকে খুঁজবে। এভাবে অল্প সময়ের মধ্যে ডিকশনারিতে যেকোনো শব্দ খুঁজে পাওয়া যায়।

বাইনারি সার্চ হলো অনেকটা এরকম একটা পদ্ধতি, যেটা ব্যবহার করে একটা সর্টেড অ্যারে থেকে কোনো একটা তথ্য খুব দ্রুত খুঁজে বের করা যায়।

লিনিয়ার সার্চ (Linear Search)

ধরো তোমার কাছে একটা অ্যারেতে অনেকগুলো সংখ্যা আছে এরকম: 100, 2, 10, 50, 20, 500, 100, 150, 200, 1000, 100

সংখ্যাগুলো এলোমেলোভাবে সাজানো থাকায় এখান থেকে একটা নির্দিষ্ট সংখ্যা খুঁজে পাওয়া সহজ না। তুমি যদি অ্যারে থেকে ৫০০ সংখ্যাটা খুঁজতে চাও তাহলে সবগুলো ইনডেক্সই পরীক্ষা করে দেখতে হবে, এটাকে বলা হয় লিনিয়ার সার্চ। অ্যারের আকার যদি $n$ হয় তাহলে লিনিয়ার সার্চের টাইম কমপ্লেক্সিটি হলো $O(n)$।

বাইনারি সার্চ (Binary Search)

কিন্তু যদি সংখ্যাগুলো নিচের মত সাজানো (Sorted) থাকে তাহলে খুঁজে পাওয়া অনেক সহজ হয়ে যায়: 2, 10, 20, 50, 100, 100, 100, 150, 200, 500, 1000

এখন যদি ১৫০ সংখ্যাটা খুঁজে বের করতে হয় তাহলে আমরা প্রথমে ঠিক মাঝের ইনডেক্সটা পরীক্ষা করবো। প্রথম ইনডেক্স ০ এবং শেষের ইনডেক্স ১০ হলে মাঝের ইনডেক্সটা হলো (০+১০)/২ বা ৫ তম ইনডেক্স।

মাঝের ইনডেক্সের সংখ্যাটা ১০০ যা ১৫০ এর থেকে ছোট, আমরা জেনে গেলাম যে সংখ্যাটা ডান পাশে কোথাও আছে, বামের অংশ আমাদের আর দরকার নাই। এখন বাকি অংশটা নিয়ে আবারো একই কাজ করবো।

বাইনারি সার্চে প্রতিবার অ্যারের ঠিক অর্ধেক অংশ আমরা বাতিল করে দিচ্ছি এবং বাকি অর্ধেক অংশে খুঁজছি। একটা সংখ্যা $n$-কে সর্বোচ্চ কয়বার ২ দিয়ে ভাগ করা যায় যতক্ষণ না সংখ্যাটা ১ হয়ে যাচ্ছে? উত্তর হলো $log_{2}n$। তাই বাইনারি সার্চে টাইম কমপ্লেক্সিটি $O(\log n)$।

Python Implementation

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        # চেক করছি মাঝখানের ভ্যালুটা target এর সমান কিনা
        if arr[mid] == target:
            return mid
            
        # target যদি বড় হয়, তাহলে ডানের অংশে খুঁজবো
        elif arr[mid] < target:
            left = mid + 1
            
        # target যদি ছোট হয়, তাহলে বামের অংশে খুঁজবো
        else:
            right = mid - 1
            
    # খুঁজে না পেলে -1 রিটার্ন করবো
    return -1

# Testing
numbers = [2, 10, 20, 50, 100, 100, 100, 150, 200, 500, 1000]
result = binary_search(numbers, 150)
print(f"Index found at: {result}")

আগামী পর্বে আমরা বাইনারি সার্চের সাহায্যে Lower Bound এবং Upper Bound বের করা শিখবো। হ্যাপি কোডিং! 🚀