সার্চিং ও সিলেকশন৬ মিনিট পড়া

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

সমস্যাটিকে অর্ধেক করে ফেলুন — এবং তা প্রতিবারই
time:\(O(\log n)\)space:\(O(1)\) ইটারেটিভ (iterative) · \(O(\log n)\) রিকার্সিভ (recursive)requirement:সাজানো বা সর্টেড (Sorted) অ্যারে

ধরুন আপনাকে ১ থেকে ১০০ এর মধ্যে একটি সংখ্যা অনুমান করতে বা গেস (guess) করতে বলা হয়েছে। ১ থেকে শুরু করে ওপরের দিকে একটি একটি করে না গিয়ে, আপনি হয়তো সরাসরি ৫০ অনুমান করলেন। সংখ্যাটি যদি বেশি বড় হয়ে যায়? তাহলে এখন আপনার ভাবনার বিষয় শুধু ১–৪৯। এরপর ২৫ অনুমান করুন। এবার কি সংখ্যাটি খুব ছোট হয়ে গেল? তাহলে আপনার নতুন রেঞ্জ হলো ২৬–৪৯। আপনার প্রতিটি অনুমান আপনার অপশনগুলোকে ঠিক অর্ধেক করে দেয়।

সংক্ষেপে এটিই হলো বাইনারি সার্চ (binary search)। প্রতিটি আইটেমকে একটি একটি করে চেক করার পরিবর্তে, আপনি সবসময় যা অবশিষ্ট থাকে তার মাঝখানের আইটেমটি চেক করবেন — এবং যে অর্ধেকাংশে আপনার উত্তরটি থাকার কোনো সম্ভাবনা নেই সেটিকে পুরোপুরি বাতিল করে দেবেন।

তবে এর একটি শর্ত আছে: লিস্টটিকে অবশ্যই সাজানো বা সর্টেড (sorted) হতে হবে। সাজানো না থাকলে আপনি বুঝতেই পারবেন না যে কোন অর্ধেকটিকে আপনি বাতিল করবেন।

এটি এত দ্রুতগতির কেন

প্রতিবার তুলনা বা কম্পারিজন করার পর, বাকি থাকা উপাদানগুলোর ঠিক অর্ধেক বাতিল হয়ে যায়। মাত্র ১০ বার তুলনা করার পরই, ১,০২৪টি উপাদানের একটি লিস্ট ছোট হয়ে মাত্র ১টিতে নেমে আসে। আর ৩০ বার তুলনা করার পর, আপনি এক বিলিয়ন বা একশ কোটি উপাদানের মধ্যে খোঁজা বা সার্চ করার কাজ শেষ করে ফেলতে পারেন। এটিই হলো \(O(\log n)\) এর মূল শক্তি।

ইটারেটিভ টেমপ্লেট (The iterative template)

দুটি পয়েন্টার (pointers) রাখুন: lo (বাম সীমানা) এবং hi (ডান সীমানা)। প্রতিটি ধাপে, mid = lo + (hi - lo) / 2 গণনা করুন — ইনটিজার ওভারফ্লো (integer overflow) এড়াতে সর্বদা এই নিয়মটিই বা সূত্রটিই ব্যবহার করবেন। যদি আপনার arr[mid] লক্ষ্য বা টার্গেটের সমান হয়, তবে আপনার কাজ শেষ। যদি এটি খুব ছোট হয়, তবে lo = mid + 1 এ সরে আসুন। আর যদি এটি খুব বড় হয়, তবে hi = mid - 1 এ সরে আসুন। যতক্ষণ lo <= hi থাকে, ততক্ষণ লুপটি বা চক্রটি চলতে দিন।

প্রথম বা শেষ উপস্থিতি খুঁজে বের করা (Finding first or last occurrence)

লিস্টে যখন একই উপাদানের ডুপ্লিকেট (duplicates) থাকে, তখন প্রথমবার মিল পেলেই থেমে যাবেন না। সবচেয়ে বামের (leftmost) উপস্থিতি খুঁজে পেতে: যখন arr[mid] == target হবে, তখন ইনডেক্সটি মনে রাখুন বা রেকর্ড করুন এবং hi = mid - 1 করে বাম দিকে খুঁজতে থাকুন। আর সবচেয়ে ডানের (rightmost) জন্য, রেকর্ড করুন এবং lo = mid + 1 করে ডান দিকে যান। এটিই মূলত সি++ (C++) এর lower_bound এবং upper_bound এর পেছনের মূল কাজ করার পদ্ধতি বা প্যাটার্ন।

Click chart to zoom
বাইনারি সার্চের সিদ্ধান্ত নেওয়ার ফ্লোচার্ট — প্রতি ইটারেশনে সার্চ করার স্পেসটিকে অর্ধেক করে ফেলা হয়
দ্রষ্টব্য: সবসময় mid এর হিসাব lo + (hi - lo) / 2 দিয়ে বের করবেন, (lo + hi) / 2 দিয়ে নয়। যখন lo এবং hi উভয়েই অনেক বড় হয়, তখন তাদের যোগফল ৩২-বিটের ইনটিজারকে ছাড়িয়ে যেতে বা ওভারফ্লো (overflow) করতে পারে — এটি একটি বিখ্যাত বাগ (bug) যা জাভার (Java) স্ট্যান্ডার্ড লাইব্রেরিতে প্রায় এক দশকেরও বেশি সময় ধরে বিদ্যমান ছিল!

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

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(arr, 23))   # 5
print(binary_search(arr, 10))   # -1
Output
5
-1

Complexity

🔍 সার্চ বা খোঁজ (ইটারেটিভ/iterative)
৩০টি ধাপে ১ বিলিয়ন উপাদান কভার করে — প্রতিটি ধাপে অবশিষ্ট খোঁজার স্থানটি বা স্পেসটি অর্ধেক হয়ে যায়
লগারিদমিক (Logarithmic) \(O(\log n)\)
🔁 সার্চ বা খোঁজ (রিকার্সিভ/recursive)
তুলনা বা কম্পারিজন একই হয়, কিন্তু প্রতিটি কল কলস্ট্যাকে (call stack) একটি করে ফ্রেম যোগ করে
একই গতি, কিন্তু বেশি মেমরি লাগে \(O(\log n)\)
💾 স্পেস বা জায়গা (ইটারেটিভ/iterative)
শুধুমাত্র lo, hi এবং mid ভেরিয়েবলগুলো (variables) থাকে — কোনো অতিরিক্ত মেমরি প্রয়োজন হয় না
কনস্ট্যান্ট (Constant) \(O(1)\)
📚 স্পেস বা জায়গা (রিকার্সিভ/recursive)
রিকার্সনের গভীরতা বা ডেপথ (depth) \(\log_2(n)\) এর সমান হয় — এক বিলিয়ন উপাদানের জন্য প্রায় ৩০টি ফ্রেম
লগারিদমিক (Logarithmic stack) \(O(\log n)\)

ছোট কুইজ

আপনি ১,০২৪ টি উপাদানের একটি সাজানো অ্যারেতে বাইনারি সার্চ করছেন। সর্বোচ্চ কতবার আপনার তুলনা বা কম্পারিজন করার প্রয়োজন হতে পারে?

পড়া চালিয়ে যান

উত্তরের ওপর বাইনারি সার্চ (Binary Search on Answer)
যখন আপনি অ্যারেতে সার্চ করতে পারেন না — তখন সরাসরি উত্তরের ওপরই সার্চ করুন
→
এক্সপোনেনশিয়াল এবং ইন্টারপোলেশন সার্চ (Exponential & Interpolation Search)
প্রথমে পরিসীমা বা রেঞ্জ খুঁজে বের করুন, তারপর সেটিতে বাইনারি সার্চ চালান
→
কুইক-সিলেক্ট (QuickSelect)
পুরোপুরি না সাজিয়েই k-তম ছোট উপাদানটি খুঁজে বের করুন
→