সার্চিং ও Divide & Conquer — অর্ধেক বাদ দিয়ে খোঁজা, ভাগ করে সমাধান

১ · দুইভাবে খোঁজা — একটি একটি করে, নাকি মাঝখান থেকে

এসএসসি-র ফল বেরিয়েছে। স্কুলের নোটিশ বোর্ডে ৮০০ জন পরীক্ষার্থীর রোল নম্বর আর গ্রেডের লম্বা তালিকা টাঙানো। আপনার রোল ৪১৭২৩৫. আপনি কী করবেন? প্রথম লাইন থেকে একটি একটি করে পড়বেন না — কারণ তালিকাটি রোল অনুযায়ী সাজানো. আপনি চোখ বুলিয়ে মাঝামাঝি কোথাও যাবেন, দেখবেন সেখানকার রোল বড় না ছোট, তারপর সেই অর্ধেকে নামবেন।

পর্ব ০২-এ ১ থেকে ১০০-এর অনুমানের খেলায় আমরা এই কৌশলটি প্রথম দেখেছিলাম। এই পর্বে সেটিকে পেশাদার স্তরে নিয়ে যাব: কীভাবে নির্ভুলভাবে লিখবেন, একই মান অনেকবার থাকলে কী করবেন, আর এমন সমস্যায় কীভাবে লাগাবেন যেখানে কোনো তালিকাই নেই।

পর্ব ৩৯-এ আমরা এই পার্থক্যকে নাম দিয়েছিলাম: linear search হলো O(n), binary search হলো O(log n). তালিকা দ্বিগুণ হলে প্রথমটির কাজও দ্বিগুণ হয়; দ্বিতীয়টির বাড়ে মাত্র একটি তুলনা।

২ · Invariant ধরে রাখুন — উত্তর থাকলে lo থেকে hi-এর ভেতরেই

Binary search-এর কোড মাত্র কয়েক লাইনের। তবু এটি প্রোগ্রামিংয়ের সবচেয়ে বেশি ভুল লেখা অ্যালগরিদমগুলোর একটি। কারণ প্রতিটি লাইনে একটি ছোট সিদ্ধান্ত থাকে — < নাকি <=, mid নাকি mid - 1. আন্দাজে লিখলে কোনো না কোনো কোণায় ভুল থেকে যায়।

সমাধান হলো আন্দাজ বাদ দিয়ে একটি প্রতিজ্ঞা ঠিক করা। পর্ব ০২-এ এর নাম শিখেছিলেন — loop invariant, লুপের প্রতিটি ঘোরার শুরুতে যে কথাটি সবসময় সত্য। Binary search-এর প্রতিজ্ঞা:

এখন প্রতিটি লাইন লেখার সময় শুধু একটি প্রশ্ন করুন: এই লাইনের পরেও কি প্রতিজ্ঞাটি সত্য থাকল? যদি a[mid] < x হয়, তাহলে mid আর তার বাঁয়ের সবগুলো x-এর চেয়ে ছোট — উত্তর সেখানে থাকতেই পারে না। তাই lo = mid + 1. ঠিক উল্টো যুক্তিতে a[mid] > x হলে hi = mid - 1. আর পরিসর ফাঁকা হয়ে গেলে (lo > hi) প্রতিজ্ঞা বলছে — x কোথাও নেই।

নিচে ১২টি সাজানো সংখ্যায় 47 খোঁজা হচ্ছে। প্রতিটি ঘরের নিচে তার index আর lo, mid, hi কোথায় আছে, দেখানো হয়েছে; লাল ঘরটি এই ধাপের mid. “পরে” চাপুন:

৩ · ছোট্ট ভুল, বড় বিপদ — off-by-one, অসীম লুপ আর overflow

Binary search লেখার দুটি জনপ্রিয় “রীতি” আছে। দুটিই ঠিক — সমস্যা হয় যখন একটির অর্ধেক আর অন্যটির অর্ধেক মিশিয়ে ফেলা হয়। AI-এর লেখা কোডেও ঠিক এই মিশ্রণ প্রায়ই দেখা যায়।

রীতি খ-এর ভিত্তি half-open range — পর্ব ১২-এর for (i = 0; i < n; i++)-এর মতোই। এবার দেখুন মিশিয়ে ফেললে কী হয়:

• while (lo <= hi) আর hi = mid: ধরুন lo = hi = 4, আর a[4] > x. mid = 4, hi = mid = 4 — কিছুই বদলাল না! পরের ঘোরাতেও একই অবস্থা। এটি একটি infinite loop; প্রোগ্রাম আটকে থাকে, কোনো error-ও দেখায় না।
• while (lo < hi) আর hi = mid - 1: লুপ থামে, কিন্তু কিছু ঘর কখনো দেখাই হয় না। ফল হলো off-by-one ভুল — বিশেষ করে শেষ বা প্রথম ঘরের মান খুঁজলে “নেই” বলে।
• lo = mid (শুধু mid, + 1 ছাড়া): দুই ঘর বাকি থাকলে, যেমন lo = 4, hi = 5, তখন mid = 4 = lo. বাঁ দিক বাদ দিতে গিয়ে lo = 4 — আবার একই জায়গায়। আবার অসীম লুপ।

যে bug প্রায় বিশ বছর লুকিয়ে ছিল

পরের সমস্যাটি আরও সূক্ষ্ম। মাঝখান বের করার সবচেয়ে স্বাভাবিক লেখা mid = (lo + hi) / 2. গণিতে এটি নির্ভুল। কিন্তু C-তে int-এর একটি সীমা আছে — সাধারণত প্রায় ২১৪ কোটি (পর্ব ০৫). array-তে যদি ১৫০ কোটি ঘর থাকে, আর lo ও hi দুটিই ১১০ কোটির বেশি হয়, তাহলে যোগফল সীমা ছাড়িয়ে যায়। একে বলে overflow. C-তে signed int-এর overflow হলো undefined behavior — বাস্তবে সাধারণত একটি ঋণাত্মক সংখ্যা তৈরি হয়, আর a[mid] পড়তে গিয়ে প্রোগ্রাম ভেঙে পড়ে।

নিরাপদ লেখা হলো mid = lo + (hi - lo) / 2. গণিতে একই মান, কিন্তু hi - lo কখনো সীমা ছাড়ায় না, আর তার অর্ধেক lo-তে যোগ করলেও ফল hi-এর চেয়ে বড় হয় না।

৪ · একই মান অনেকবার — lower_bound ও upper_bound

ক্লাসের ১০ জন ছাত্রের নম্বর সাজানো আছে: 12, 25, 25, 25, 25, 25, 38, 40, 47, 55. প্রশ্ন: ঠিক 25 পেয়েছে কতজন? সাধারণ binary search বলবে “25 আছে” — কিন্তু কোন 25? প্রথম ধাপেই মাঝের কোনো একটি 25 পেয়ে থেমে যাবে। গণনার জন্য আমাদের লাগবে প্রথম 25 কোথায় আর শেষ 25-এর পরে কী।

এখানে প্রতিজ্ঞাটি একটু বদলাতে হয়। lower_bound-এর জন্য রীতি খ ([lo, hi)) সবচেয়ে পরিষ্কার, আর invariant দুই ভাগে: “lo-এর বাঁয়ের সব মান < x, আর hi ও তার ডানের সব মান ≥ x.” মাঝের [lo, hi) অংশটি অজানা। প্রতি ধাপে অজানা অংশ ছোট হয়; শেষে lo == hi হলে আর কিছু অজানা নেই, আর সেই সীমানাটিই উত্তর।

এবার কোডে। একটি lower_bound ফাংশন লিখে তা দিয়েই গণনা করা হয়েছে। integer-এর ক্ষেত্রে “প্রথম > 25” আর “প্রথম ≥ 26” একই জিনিস — তাই upper_bound-এর জন্য আলাদা ফাংশন না লিখে lower_bound(26) ডাকা হয়েছে:

#include <stdio.h>

/* first i with a[i] >= x (n if none). invariant: a[<lo] < x, a[>=hi] >= x */
int lower_bound(const int a[], int n, int x) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;      /* safe from overflow */
        if (a[mid] < x) lo = mid + 1;      /* mid is too small */
        else            hi = mid;          /* mid may be the answer */
    }
    return lo;                             /* here lo == hi */
}

int main(void) {
    int marks[] = {12, 25, 25, 25, 25, 25, 38, 40, 47, 55};
    int n = sizeof marks / sizeof marks[0];
    int first = lower_bound(marks, n, 25), past = lower_bound(marks, n, 26);
    printf("first 25 at index %d, count = %d\n", first, past - first);
    printf("lb(30) = %d, lb(99) = %d\n", lower_bound(marks, n, 30), lower_bound(marks, n, 99));
    return 0;
}

৫ · উত্তরের ওপর binary search — হ্যাঁ/না প্রশ্নের সীমানা খোঁজা

এখন পর্যন্ত আমরা একটি array-তে খুঁজেছি। এবার এমন একটি সমস্যা দেখি, যেখানে কোনো সাজানো তালিকাই নেই — অথচ binary search সবচেয়ে সুন্দরভাবে কাজ করে।

গাজীপুরের একটি গার্মেন্টস কারখানা থেকে ৭টি চালান চট্টগ্রাম বন্দরে যাবে। ওজন (টনে), জাহাজে তোলার ক্রম অনুযায়ী: 5, 8, 3, 6, 4, 7, 2. একটি ট্রাক দিনে একবার যায়, আর চালানগুলো ক্রম ভেঙে পাঠানো যাবে না। সব চালান ৩ দিনের মধ্যে পৌঁছাতে হবে। প্রশ্ন: সবচেয়ে কম কত টনের ট্রাক ভাড়া নিলে চলবে? বড় ট্রাকের ভাড়া বেশি, তাই যত ছোট সম্ভব।

মূল কৌশল হলো প্রশ্নটি উল্টে দেওয়া। “সবচেয়ে কম কত?” না জিজ্ঞেস করে জিজ্ঞেস করুন: “C টনের ট্রাকে কি ৩ দিনে হবে?” এই হ্যাঁ/না প্রশ্নের উত্তর দেওয়া সহজ: চালানগুলো ক্রমে ট্রাকে তুলুন, ধরে না রাখলে পরের দিন — শেষে দিন গুনুন।

আর এই প্রশ্নের একটি অসাধারণ বৈশিষ্ট্য আছে: ১২ টনে যদি হয়, ১৩ টনে অবশ্যই হবে — বড় ট্রাক কখনো ক্ষতি করে না। অর্থাৎ ক্ষমতা বাড়ালে উত্তর একবার “না” থেকে “হ্যাঁ” হলে আর কখনো “না” হয় না:

এমন একমুখী আচরণকে বলে monotonic. আর monotonic হ্যাঁ/না প্রশ্নের প্রথম “হ্যাঁ”-টি খোঁজা আর সাজানো তালিকায় lower_bound খোঁজা হুবহু একই কাজ! এই কৌশলের নাম binary search on the answer. সম্ভাব্য উত্তরের সীমাও সহজে পাওয়া যায়: সবচেয়ে ভারী চালান 8 টন, তাই 8-এর কম চলবেই না; আর মোট ওজন 35 টন হলে একদিনেই সব যায়, তাই 35-এ অবশ্যই চলবে।

কোডে দুটি অংশ পরিষ্কার আলাদা: একটি সাধারণ হ্যাঁ/না ফাংশন, আর তার ওপর lower_bound-এর মতো একটি লুপ। এই ধরনের হ্যাঁ/না ফাংশনকে বলে predicate:

#include <stdio.h>

/* yes/no: can a `cap`-ton truck ship all, in order, within `days`? (cap >= heaviest) */
int can_ship(const int w[], int n, int cap, int days) {
    int used = 1, load = 0;
    for (int i = 0; i < n; i++)                       /* new day if it does not fit */
        if (load + w[i] > cap) { used++; load = w[i]; } else load += w[i];
    return used <= days;
}

int main(void) {
    int w[] = {5, 8, 3, 6, 4, 7, 2}, n = 7, days = 3;
    int lo = 8, hi = 35;                 /* heaviest shipment .. total weight */
    while (lo < hi) {                    /* smallest good cap is in [lo, hi] */
        int mid = lo + (hi - lo) / 2;
        if (can_ship(w, n, mid, days)) hi = mid;   /* mid works: maybe smaller works */
        else                           lo = mid + 1; /* mid fails: need bigger */
    }
    printf("minimum truck capacity = %d tons\n", lo);
    return 0;
}

৬ · C library-র bsearch() — তৈরি করা হাতিয়ার

পর্ব ২৮-এ আপনি <stdlib.h>-এর qsort দেখেছিলেন, যে comparator ফাংশন নিয়ে যেকোনো টাইপের array সাজায়। একই ঘরানার একটি খোঁজার ফাংশনও আছে — bsearch:

void *bsearch(const void *key, const void *base, size_t n, size_t size,
              int (*cmp)(const void *, const void *));

int cmp_int(const void *p, const void *q) {
    int a = *(const int *)p, b = *(const int *)q;
    return (a > b) - (a < b);            /* -1, 0 or 1, never overflows */
}
int x = 25;
int *hit = bsearch(&x, marks, n, sizeof marks[0], cmp_int);   /* NULL if absent */

এটি পাওয়া গেলে মিলে যাওয়া ঘরের একটি pointer দেয়, না পেলে NULL. index দরকার হলে hit - marks (পর্ব ১৮-এর pointer arithmetic). আর qsort-এর জন্য লেখা comparator-টিই এখানে কাজ করবে — শুধু খেয়াল রাখুন, array ঠিক সেই comparator দিয়েই সাজানো থাকতে হবে।

৭ · Divide & Conquer — ভাগ করুন, সমাধান করুন, জোড়া দিন

Binary search আসলে একটি বড় চিন্তার সবচেয়ে সরল রূপ: সমস্যাটিকে ছোট করা, তারপর ছোটটির সমাধান থেকে বড়টির সমাধান বানানো। এই চিন্তার নাম divide and conquer, আর এর একটি নির্দিষ্ট রেসিপি আছে:

পর্ব ৪০-এর merge sort এই রেসিপির নিখুঁত উদাহরণ: array-কে দুই ভাগ করুন, প্রতিটি ভাগ merge sort দিয়েই সাজান, তারপর দুটি সাজানো ভাগকে একটি চিরুনির মতো মিলিয়ে দিন। ভাগ করাটা সহজ, জোড়া দেওয়াটাই আসল কাজ। Binary search-এ উল্টো — ভাগের পর একটি ভাগই রাখা হয়, অন্যটি ফেলে দেওয়া হয়, আর জোড়ার কাজ নেই।

দ্রুত ঘাত — xⁿ মাত্র log n ধাপে

3¹³ বের করতে সাধারণ লুপে ১২টি গুণ লাগে। কিন্তু একটি পর্যবেক্ষণ খেয়াল করুন: n জোড় হলে xⁿ = (x^n/2)². অর্থাৎ x^n/2 একবার হিসাব করে নিজের সাথে গুণ করলেই হলো। n বিজোড় হলে একটি বাড়তি x গুণ করতে হয়। এই কৌশলের নাম fast power (exponentiation by squaring):

long long power(long long x, int n) {        /* n >= 0 */
    if (n == 0) return 1;                     /* base case */
    long long half = power(x, n / 2);         /* divide: ONE smaller problem */
    return (n % 2 == 0) ? half * half         /* combine */
                        : half * half * x;
}

১২টির জায়গায় মোট ৭টি গুণ, তার দুটি আবার 1 × 1-এর মতো তুচ্ছ। পার্থক্যটা বড় n-এ নাটকীয়: n = ১০ লাখ হলে সাধারণ লুপে প্রায় ১০ লাখ গুণ, আর এখানে বড়জোর ৪০টির মতো — কারণ ১০ লাখকে বারবার অর্ধেক করলে ২০ ধাপেই ১-এ নামে। খেয়াল করুন, half ভ্যারিয়েবলটিই আসল চাবি: power(x, n/2) * power(x, n/2) লিখলে একই কাজ দুবার হতো, আর সব লাভ হারিয়ে যেত। (এত বড় ঘাতে long long অবশ্যই overflow করবে; বাস্তবে প্রতিটি গুণের পর % m নেওয়া হয় — এই “modular exponentiation” RSA-র মতো এনক্রিপশনের ভিত্তি।)

আরও কয়েকটি বিখ্যাত divide and conquer

৮ · খরচের হিসাব — recursion tree আর n log n

Recursive অ্যালগরিদমের খরচ কীভাবে মাপবেন? নিজেকে ডাকা ফাংশনের খরচ নিজের ভাষাতেই লেখা যায়। merge sort-এ n আকারের কাজ = দুটি n/2 আকারের কাজ + জোড়ার জন্য প্রায় n ধাপ:

এ রকম সমীকরণকে বলে recurrence. এটি সমাধানের সবচেয়ে সহজ ও চোখে দেখার মতো উপায় হলো একটি recursion tree আঁকা — প্রতিটি ডাক একটি ঘর, তার নিচে সে যাদের ডাকে। তারপর প্রতিটি স্তরের কাজ যোগ করুন। n = 8 দিয়ে দেখি:

একই কৌশলে binary search-এর হিসাবও মেলে: প্রতি ধাপে একটি অর্ধেক সমস্যা আর একটি তুলনা — T(n) = T(n/2) + 1. Recursion tree-টি একটি সোজা লাঠি, log n স্তর, প্রতি স্তরে ১টি কাজ — মোট log n. দ্রুত ঘাতেরও একই গঠন।

৯ · বাস্তব জগতে — git bisect, অর্ধেক করে debugging, ডেটাবেস index

Binary search শুধু array-র অ্যালগরিদম নয় — এটি একটি চিন্তার অভ্যাস। পেশাদার প্রকৌশলীরা প্রতিদিন এমন জায়গায় এটি ব্যবহার করেন, যেখানে কোনো কোডই লেখা নেই।

git bisect — কোন commit bug আনল?

পর্ব ২৯-এ আপনি git দেখেছিলেন। ধরুন গত মাসে আপনার প্রজেক্ট ঠিক চলছিল, আজ চলছে না, আর মাঝে ৫০০টি commit হয়েছে। কোনটি ভুল ঢোকাল? প্রতিটি commit পরীক্ষা করার বদলে git bisect মাঝখানের commit-এ নিয়ে যায়; আপনি চালিয়ে বলেন “ঠিক” বা “ভুল”, আর git অর্ধেক বাদ দেয়। ৫০০টি commit-এ মোটামুটি ৯টি পরীক্ষাতেই দোষী commit ধরা পড়ে।

git bisect start
git bisect bad                 # current version is broken
git bisect good v2.3           # this older version worked
# git checks out a middle commit; build, test, then tell it:
git bisect good                # or: git bisect bad
# ... repeat until git prints "<hash> is the first bad commit"
git bisect run ./test.sh       # or let a script answer good/bad automatically
git bisect reset               # go back to where you started

লক্ষ করুন, এখানেও একটি monotonic প্রশ্ন আছে: “এই commit-এ কি bug আছে?” bug একবার ঢুকলে পরের সব commit-এই থাকে (যদি মাঝে কেউ ঠিক না করে)। তাই “ঠিক, ঠিক, ঠিক, ভুল, ভুল, ভুল” — আর প্রথম “ভুল”-টি খোঁজা মানে lower_bound!

অর্ধেক করে debugging

একটি ১০,০০০ লাইনের CSV ফাইল দিলে প্রোগ্রাম crash করে, ছোট ফাইলে করে না। কোন লাইনটি দোষী? ফাইলটি অর্ধেক করে দুটি ভাগ আলাদাভাবে দিন। যে ভাগে crash, সেটিকে আবার অর্ধেক। প্রায় ১৪ বারে একটি লাইনে পৌঁছাবেন। একই কৌশল কোডেও চলে: অর্ধেক কোড সাময়িকভাবে বাদ দিয়ে দেখুন সমস্যা থাকে কি না, অথবা মাঝখানে একটি printf বসিয়ে দেখুন সেখানে মান ঠিক আছে কি না। দিশাহীনভাবে খোঁজার চেয়ে এটি অনেক দ্রুত, আর নিশ্চিতভাবে কোথাও পৌঁছায়।

ডেটাবেস index — B-tree-র ভেতরে binary search

bKash বা কোনো ব্যাংকের ডেটাবেসে কোটি কোটি লেনদেন। একটি মোবাইল নম্বরের লেনদেন খুঁজতে পুরো টেবিল পড়লে বহু সেকেন্ড লেগে যেত। তাই ডেটাবেস index তৈরি করে — সাধারণত একটি B-tree (পর্ব ৩৫). এর প্রতিটি node-এ শত শত সাজানো চাবি থাকে; node-এর ভেতরে binary search দিয়ে ঠিক করা হয় কোন শাখায় নামতে হবে। প্রতিটি node অনেক শাখায় ভাগ হয় বলে কোটি সারির টেবিলেও গাছের উচ্চতা মাত্র কয়েক স্তর — অর্থাৎ ডিস্ক থেকে মাত্র কয়েকবার পড়েই উত্তর।

১০ · AI-এর যুগে binary search যাচাই

AI-কে “binary search লিখে দাও” বললে কয়েক সেকেন্ডে পরিপাটি কোড আসে, আর সাধারণ পরীক্ষায় সেটি ঠিকই চলে। সমস্যা লুকিয়ে থাকে কিনারায় — এক ঘরের array-তে, প্রথম বা শেষ ঘরে, বা একই মান অনেকবার থাকলে। এই অ্যালগরিদম ঠিক সেই জাতের, যেখানে “দেখতে ঠিক” আর “আসলেই ঠিক”-এর মধ্যে দূরত্ব সবচেয়ে বেশি।

AI-এর binary search হাতে পেলে — যাচাইয়ের চেকলিস্ট

• পরিসরের রীতি মিলিয়ে দেখেছি — [lo, hi] হলে lo <= hi ও hi = mid - 1; [lo, hi) হলে lo < hi ও hi = mid
• প্রতিটি শাখায় খোঁজার জায়গা অন্তত এক ঘর ছোট হচ্ছে, নিশ্চিত হয়েছি (lo = mid কোথাও নেই)
• mid = lo + (hi - lo) / 2 — যোগ করে ভাগ নয়
• খালি array, এক ঘর, দুই ঘর, সব মান সমান, নেই এমন মান, প্রথম ও শেষ ঘর — সবগুলোতে চালিয়েছি
• একটি সাধারণ linear search-এর সাথে হাজারখানেক এলোমেলো ইনপুটে ফল মিলিয়ে দেখেছি
• ইনপুট সত্যিই সাজানো কি না, আর একই comparator দিয়ে সাজানো কি না, যাচাই করেছি