Linear আর binary search

১ · খোঁজার প্রথম পথ — linear search আর কখন সেটিই ঠিক

পরীক্ষার হলে খাতা জমা দেওয়ার পর পরিদর্শক স্যারের টেবিলে ৬০টি খাতা এলোমেলো স্তূপ হয়ে আছে। এখন রোল ৩৭-এর খাতাটি দরকার। স্যার কী করবেন? ওপর থেকে একটি একটি খাতা তুলে রোল দেখবেন — পেলে থামবেন, না পেলে শেষ পর্যন্ত যাবেন। খাতাগুলো সাজানো নেই, তাই এর চেয়ে বুদ্ধিমান কোনো পথ নেই। এটিই linear search: শুরু থেকে প্রতিটি উপাদান লক্ষ্যের (x) সাথে মিলিয়ে দেখা।

Pseudocode (0-based): linear search

LINEAR-SEARCH(a, n, x):
    for i = 0 to n - 1:
        if a[i] == x: return i      // found: first position
    return -1                       // checked all n, not present

বিশ্লেষণ সোজা (পর্ব ০৫-এর ভাষায়): best case-এ x প্রথম ঘরেই, Θ(1). worst case-এ x শেষ ঘরে বা নেই — n টি তুলনা, Θ(n). x অ্যারেতে আছে আর প্রতিটি অবস্থান সমান সম্ভাব্য ধরলে গড়ে (n + 1)/2 টি তুলনা, তাও Θ(n). বাড়তি জায়গা O(1).

কখন linear search-ই সঠিক পছন্দ

• ডেটা সাজানো নয়, আর মাত্র একবার বা কয়েকবার খুঁজবেন। সাজাতে লাগে O(n log n) (পর্ব ২১–২২) — একটি খোঁজার জন্য সেটি linear search-এর চেয়ে বেশি খরচ। অনেকবার খুঁজতে হলে তখন সাজিয়ে নেওয়া (বা hash table, পর্ব ৩২) লাভজনক।
• অ্যারে খুব ছোট। দশ-বিশটি উপাদানে linear search-এর লুপ এত সরল যে আধুনিক CPU-তে তা প্রায়ই binary search-এর সমান বা দ্রুত — মেমরি পাশাপাশি পড়া হয় (পর্ব ১০-এর cache), আর শাখা (branch) অনুমান করা সহজ।
• Linked list. পর্ব ১২-এ দেখেছেন, linked list-এ k-তম node-এ যেতে k টি ধাপ লাগে। সাজানো linked list-এও “মাঝখানে যাওয়া” O(n), তাই binary search-এর কোনো লাভ থাকে না — linear search-ই স্বাভাবিক।
• শর্তটি তুলনা নয়। “প্রথম জোড় সংখ্যা”, “প্রথম যে গ্রাহকের বকেয়া আছে” — এমন খোঁজায় ক্রম কাজে লাগে না, তাই প্রতিটি দেখতে হয়।

Sentinel কৌশল — প্রতি ধাপে একটি তুলনা কম

ওপরের লুপে প্রতিটি ঘোরায় আসলে দুটি তুলনা হয়: i < n (সীমা পেরোলাম কি না) আর a[i] == x. Donald Knuth তাঁর “The Art of Computer Programming”-এর তৃতীয় খণ্ডে একটি পুরোনো কৌশল দেখান: অ্যারের শেষে একটি বাড়তি ঘরে x নিজেই বসিয়ে দিন। এই বসানো মানটিকে বলে sentinel (পাহারাদার)। এখন লুপ নিশ্চিতভাবে কোথাও না কোথাও x পাবে, তাই সীমার পরীক্ষা লাগে না:

Pseudocode (0-based): linear search with a sentinel; a has room for a[n]

SENTINEL-SEARCH(a, n, x):
    a[n] = x                        // the sentinel guarantees a stop
    i = 0
    while a[i] != x:                // ONE comparison per step
        i = i + 1
    return (i < n) ? i : -1         // stopped at the sentinel = not found

Complexity একই Θ(n) — শুধু ধ্রুবকটি ছোট। পর্ব ১২-এর sentinel node-এর মতোই ভাবনা: একটি নকল উপাদান বসিয়ে সীমানার বিশেষ পরীক্ষা মুছে ফেলা। তবে খেয়াল রাখুন, এতে অ্যারে বদলায় (বাড়তি ঘর লাগে, আর একসাথে কয়েকটি thread পড়লে বিপদ), আর আধুনিক compiler প্রায়ই সাধারণ লুপকেই ভালোভাবে অপ্টিমাইজ করে। তাই এটি পরীক্ষার আর ইন্টারভিউর প্রিয় প্রশ্ন, কিন্তু দৈনন্দিন কোডে খুব কম দরকার হয়।

২ · Binary search-এর ধারণা — অভিধান আর ফোনবুক

ইংরেজি-বাংলা অভিধানে “monsoon” শব্দটি খুঁজছেন। আপনি কি প্রথম পাতা থেকে একটি একটি করে উল্টাবেন? না। মাঝামাঝি একটি পাতা খুলবেন — দেখলেন “label”. “monsoon” বর্ণক্রমে পরে, তাই বাঁয়ের পুরো অর্ধেক মন থেকে মুছে ফেললেন। ডান অর্ধেকের মাঝে খুললেন — “river”, এবার আগে, তাই ডানের অংশ বাদ। প্রতিবার একটি পাতা দেখে বাকি অংশের অর্ধেক বাদ। পুরোনো দিনের ছাপা টেলিফোন ডিরেক্টরিতে নাম খোঁজাও ঠিক এমন। এটিই binary search.

এই কৌশলের একটিমাত্র শর্ত (precondition): অ্যারে সাজানো থাকতে হবে। সাজানো বলেই একটি তুলনা থেকে অনেক কিছু জানা যায়: a[mid] < x হলে a[0..mid]-এর সবাই ≤ a[mid] < x — একটি তুলনায় mid + 1 টি ঘর বাদ। এলোমেলো অ্যারেতে a[mid] দেখে বাকিদের সম্পর্কে কিছুই বলা যায় না।

পর্ব ০৬-এ দেখেছেন, log₂ n মানে “n-কে কতবার অর্ধেক করলে ১-এ পৌঁছায়”। বাংলাদেশের প্রায় ১৭ কোটি মানুষের একটি সাজানো তালিকাতেও একজনকে খুঁজতে ২৮টি ধাপই যথেষ্ট। n দ্বিগুণ হলে binary search-এর কাজ বাড়ে মাত্র একটি ধাপ — এটিই logarithmic time-এর শক্তি।

৩ · তিনটি ছাঁচ আর একটি প্রমাণিত টেমপ্লেট

ধারণা এক বাক্যের, কিন্তু কোড লেখা কুখ্যাতভাবে কঠিন — পর্ব ০৩-এ Jon Bentley আর Donald Knuth-এর পর্যবেক্ষণ দেখেছেন। গোলমালের মূলে চারটি ছোট সিদ্ধান্ত: hi শুরুতে n নাকি n − 1? শর্ত lo < hi নাকি lo <= hi? hi = mid নাকি mid − 1? শেষে কী ফেরত দেব? এই চারটি একে অপরের সাথে বাঁধা — একটি বদলালে বাকিগুলোও বদলাতে হয়। প্রচলিত তিনটি ছাঁচ পাশাপাশি দেখুন:

তিনটিই ঠিক — যদি নিজের ভেতরে সংগত থাকে। বিপদ হয় মিশিয়ে ফেললে: ছাঁচ খ-এর hi = mid আর ছাঁচ ক-এর lo <= hi একসাথে লিখলে lo = hi = mid অবস্থায় লুপ চিরকাল ঘোরে। আমরা ছাঁচ খ-কে প্রধান টেমপ্লেট হিসেবে নেব, তিনটি কারণে: (১) এটি সবসময় একটি অর্থপূর্ণ উত্তর দেয়, x না থাকলেও; (২) সদৃশ মান থাকলেও ঠিক কোন অবস্থান আসবে, তা নির্দিষ্ট; (৩) C++-এর std::lower_bound আর Python-এর bisect_left হুবহু এটিই (পর্ব ১৫)। প্রশ্নটিকে লিখি একটি একমুখী (monotone) হ্যাঁ/না শর্ত হিসেবে:

সাজানো অ্যারেতে “a[i] ≥ x” শর্তটি বাঁ দিকে সব “না”, তারপর এক জায়গা থেকে সব “হ্যাঁ” — না, না, না, হ্যাঁ, হ্যাঁ। এমন শর্তকে বলে monotonic predicate. Binary search আসলে এই “না → হ্যাঁ” সীমানাটি খোঁজে; x-এর সমান মান থাকুক বা না থাকুক।

Pseudocode (0-based; a[0..n-1] sorted ascending; half-open range [lo, hi))

LOWER-BOUND(a, n, x):                  // first i with a[i] >= x, or n
    lo = 0, hi = n
    while lo < hi:                     // range [lo, hi) not empty
        mid = lo + (hi - lo) / 2       // integer division; lo <= mid < hi
        if a[mid] < x: lo = mid + 1    // a[0..mid] all < x
        else:          hi = mid        // a[mid..n-1] all >= x
    return lo                          // lo == hi == the boundary

FOUND?  lo < n and a[lo] == x

প্রমাণ (পর্ব ০৩-এর তিন ধাপ + termination).

• Initialization: lo = 0, hi = n. a[0..0) আর a[n..n) দুটিই খালি — খালি সেট সম্পর্কে যেকোনো “সবাই” দাবি সত্য।
• Maintenance: lo < hi বলে mid = lo + ⌊(hi − lo)/2⌋ মানে lo ≤ mid < hi, তাই a[mid] বৈধ ঘর। যদি a[mid] < x, সাজানো বলে a[lo..mid]-এর সবাই ≤ a[mid] < x; তাই lo = mid + 1 করলেও “a[0..lo) < x” টেকে। নইলে a[mid] ≥ x, তাই a[mid..n)-এর সবাই ≥ x; hi = mid করলে “a[hi..n) ≥ x” টেকে।
• Termination: পরিমাপ hi − lo প্রতি ঘোরায় কঠোরভাবে কমে (mid + 1 > lo, আর mid < hi), কখনো ঋণাত্মক হয় না — তাই লুপ থামে (পর্ব ০৩-এর variant function). থামার সময় lo = hi. Invariant বলছে বাঁয়ের সবাই < x, ডান থেকে সবাই ≥ x — অর্থাৎ lo-ই প্রথম ঘর যেখানে a[i] ≥ x (বা n, যদি এমন ঘর নেই)। ∎

লক্ষ করুন, প্রমাণ থেকেই প্রতিটি লাইন বেরিয়েছে: hi = mid (mid − 1 নয়) কারণ a[mid] নিজেই উত্তর হতে পারে; lo = mid + 1 কারণ a[mid] নিশ্চিতভাবে উত্তর নয়; শর্ত lo < hi কারণ lo = hi মানে অজানা অংশ খালি। নিচে a = [3, 8, 15, 21, 27, 34, 42, 56] (n = 8)-এ x = 27 খুঁজে দেখুন। “mark” সারিতে < মানে “জানা গেছে a[i] < x”, ≥ মানে “জানা গেছে a[i] ≥ x”, ? মানে এখনো অজানা:

1int lo = 0, hi = n;2while (lo < hi) {3    int mid = lo + (hi - lo) / 2;4    if (a[mid] < x) lo = mid + 1;5    else            hi = mid;6}7return lo;  // found if a[lo] == x

এবার একই অ্যারেতে x = 30 — যা অ্যারেতে নেই। বন্ধ ছাঁচে উত্তর হতো শুধু “−1”; half-open টেমপ্লেট বলে দেয় 30 কোথায় থাকা উচিত ছিল:

৪ · mid-এর ফাঁদ — overflow আর সঠিক মাঝবিন্দু

বহু বইয়ে মাঝের ঘর লেখা হয় mid = (lo + hi) / 2. গণিতে এটি নিখুঁত। কিন্তু C++ বা Java-তে lo আর hi যদি 32-bit int হয়, তাহলে lo + hi যোগফলটি int-এর সীমা 2,147,483,647 (প্রায় 2.1 × 10⁹) ছাড়াতে পারে — যদিও lo আর hi দুটিই বৈধ সূচক। ধরুন অ্যারেতে ১৫০ কোটি উপাদান, lo = 1,200,000,000 আর hi = 1,500,000,000. যোগফল 2.7 × 10⁹ — integer overflow. C++-এ signed overflow undefined behaviour; বাস্তবে সাধারণত মান ঘুরে ঋণাত্মক হয়, আর a[mid] অ্যারের বাইরে পড়ে।

২০০৬ সালে Joshua Bloch তাঁর ব্লগে দেখান যে Java-র লাইব্রেরির Arrays.binarySearch-এ ঠিক এই লাইনটি বহু বছর ধরে ছিল — আর Jon Bentley-র “Programming Pearls”-এর বিখ্যাত সংস্করণেও একই ধরন। বাগটি ধরা পড়তে এত দেরি হয়েছিল কারণ ২³⁰-এর বেশি উপাদানের অ্যারে তখন বিরল ছিল। (গল্পের বিস্তারিত পর্ব ০৩-এর ভাবনার প্রশ্ন ২-এ।) সমাধান সহজ:

কেন এটি নিরাপদ? 0 ≤ lo ≤ hi বলে hi − lo ≥ 0 আর hi − lo ≤ hi, তাই কোনো মধ্যবর্তী মান hi-কে ছাড়ায় না। ফলও একই: lo + ⌊(hi − lo)/2⌋ = ⌊(lo + hi)/2⌋. অন্য বিকল্পগুলো:

• C++20: std::midpoint(lo, hi) (হেডার <numeric>) — overflow ছাড়া মাঝবিন্দু, ঋণাত্মক মানেও।
• Java: (lo + hi) >>> 1 — যোগফল overflow করলেও unsigned shift সঠিক ধনাত্মক ফল দেয়। Bloch-এর লেখায় এটিও প্রস্তাবিত।
• Python: integer-এর আকার সীমাহীন, তাই (lo + hi) // 2 নিরাপদ। তবু অভ্যাসটি রাখুন — ভাষা বদলালে কাজে দেবে।

৫ · এক টেমপ্লেটে সব প্রশ্ন — lower bound, upper bound, গণনা আর অবস্থান

বাস্তবে প্রশ্ন শুধু “x আছে কি না” নয়। একটি অনলাইন দোকানের দাম-সাজানো তালিকায় প্রশ্ন আসে: “৫০০ টাকা বা তার বেশি দামের প্রথম জিনিস কোনটি?”, “ঠিক ৫০০ টাকার জিনিস কয়টি?”, “৫০০-এর কম দামের সবচেয়ে দামি কোনটি?” সব প্রশ্নের উত্তর দুটি সীমানা থেকে আসে। দ্বিতীয় সীমানাটি upper bound:

কোডে পার্থক্য একটিমাত্র চিহ্ন: a[mid] < x-এর বদলে a[mid] <= x. Invariant-ও একইভাবে বদলায়: “a[0..lo) ≤ x, a[hi..n) > x”. সাজানো অ্যারেতে x-এর সব কপি পাশাপাশি থাকে, ঠিক [lower_bound, upper_bound) পরিসরে। এখান থেকে সব উত্তর:

লাইব্রেরিতে এগুলো তৈরি আছে (পর্ব ১৫): C++-এ std::lower_bound আর std::upper_bound একটি iterator দেয়, সূচক পেতে - a.begin(); std::equal_range একবারে দুটিই দেয়। Python-এর bisect মডিউলে bisect_left = lower bound আর bisect_right = upper bound. নিচের কোডে নিজের লেখা দুটি ফাংশন একটি নির্দিষ্ট অ্যারেতে চালিয়ে প্রতিটি ফল লাইব্রেরির সাথে মিলিয়ে নেওয়া হয়েছে:

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cassert>
#include <initializer_list>
using namespace std;

int lowerBound(const vector<int>& a, int x) {  // first i with a[i] >= x, or n
    int lo = 0, hi = (int)a.size();             // a[0..lo) < x <= a[hi..n)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;           // never overflows
        if (a[mid] < x) lo = mid + 1; else hi = mid;
    }
    return lo;
}
int upperBound(const vector<int>& a, int x) {  // first i with a[i] > x, or n
    int lo = 0, hi = (int)a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= x) lo = mid + 1; else hi = mid;   // only change: <=
    }
    return lo;
}
int main() {
    vector<int> a = {1, 3, 3, 3, 5, 8, 8, 13};
    for (int x : {3, 8, 4, 0, 13, 20}) {
        int lb = lowerBound(a, x), ub = upperBound(a, x);
        assert(lb == lower_bound(a.begin(), a.end(), x) - a.begin() &&
               ub == upper_bound(a.begin(), a.end(), x) - a.begin());
        int cnt = ub - lb, first = cnt ? lb : -1, last = cnt ? ub - 1 : -1;
        cout << "x=" << setw(2) << x << ": lower=" << lb << " upper=" << ub
             << " count=" << cnt << " first=" << first << " last=" << last << '\n';
    }
    cout << "all results match the library\n";
}

x= 3: lower=1 upper=4 count=3 first=1 last=3
x= 8: lower=5 upper=7 count=2 first=5 last=6
x= 4: lower=4 upper=4 count=0 first=-1 last=-1
x= 0: lower=0 upper=0 count=0 first=-1 last=-1
x=13: lower=7 upper=8 count=1 first=7 last=7
x=20: lower=8 upper=8 count=0 first=-1 last=-1
all results match the library

from bisect import bisect_left, bisect_right

def lower_bound(a, x):            # first i with a[i] >= x, or len(a)
    lo, hi = 0, len(a)            # invariant: a[:lo] < x <= a[hi:]
    while lo < hi:
        mid = (lo + hi) // 2      # Python ints never overflow
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

def upper_bound(a, x):            # first i with a[i] > x, or len(a)
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= x:           # the only change: <= instead of <
            lo = mid + 1
        else:
            hi = mid
    return lo

a = [1, 3, 3, 3, 5, 8, 8, 13]
for x in [3, 8, 4, 0, 13, 20]:
    lb, ub = lower_bound(a, x), upper_bound(a, x)
    assert (lb, ub) == (bisect_left(a, x), bisect_right(a, x))
    cnt = ub - lb
    first, last = (lb, ub - 1) if cnt else (-1, -1)
    print(f"x={x:2}: lower={lb} upper={ub} count={cnt} first={first} last={last}")
print("all results match the library")

x= 3: lower=1 upper=4 count=3 first=1 last=3
x= 8: lower=5 upper=7 count=2 first=5 last=6
x= 4: lower=4 upper=4 count=0 first=-1 last=-1
x= 0: lower=0 upper=0 count=0 first=-1 last=-1
x=13: lower=7 upper=8 count=1 first=7 last=7
x=20: lower=8 upper=8 count=0 first=-1 last=-1
all results match the library

৬ · পুরোপুরি সাজানো নয়, তবু binary search — rotated array আর peak element

Binary search-এর আসল শর্ত “পুরো অ্যারে সাজানো” নয়; শর্ত হলো — একটি তুলনা থেকে নিশ্চিতভাবে বলা যাওয়া কোন অর্ধেক বাদ দেওয়া নিরাপদ। দুটি বিখ্যাত ইন্টারভিউ-সমস্যায় এটি দেখা যায়।

Rotated sorted array-তে খোঁজা

একটি সাজানো অ্যারেকে কোনো এক জায়গা থেকে কেটে সামনের অংশ পেছনে জুড়ে দিলে পাওয়া যায় rotated sorted array: [5, 10, 20, 30, 40, 50, 60] থেকে [30, 40, 50, 60, 5, 10, 20]. ভাবুন একটি গোল ঘড়ির মতো সাজানো সময়সূচি, যেটি মাঝরাতের বদলে অন্য কোনো সময় থেকে শুরু হয়েছে। এখানে উপাদানগুলো আলাদা (distinct) ধরে নিচ্ছি।

মূল পর্যবেক্ষণ: যেকোনো mid-এ দুই অর্ধেক a[lo..mid] আর a[mid..hi]-এর অন্তত একটি পুরোপুরি সাজানো, কারণ “ভাঙার জায়গা” (বড় থেকে হঠাৎ ছোট) একটিই, আর সেটি দুই অর্ধেকের একটিতেই পড়ে। কোনটি সাজানো তা এক তুলনায় জানা যায়: a[lo] ≤ a[mid] হলে বাঁ অর্ধেক। সাজানো অর্ধেকের দুই প্রান্ত দেখে বলা যায় x সেখানে থাকতে পারে কি না — পারলে সেদিকে যাই, না পারলে অন্য দিকে। বন্ধ ছাঁচ [lo, hi] এখানে স্বাভাবিক, কারণ আমরা একটি নির্দিষ্ট মান খুঁজছি:

Pseudocode (0-based; distinct values; closed range [lo, hi])

SEARCH-ROTATED(a, n, x):
    lo = 0, hi = n - 1
    while lo <= hi:
        mid = lo + (hi - lo) / 2
        if a[mid] == x: return mid
        if a[lo] <= a[mid]:                       // left part a[lo..mid] sorted
            if a[lo] <= x < a[mid]: hi = mid - 1
            else:                   lo = mid + 1
        else:                                      // right part a[mid..hi] sorted
            if a[mid] < x <= a[hi]: lo = mid + 1
            else:                   hi = mid - 1
    return -1

একই ভাবনায় “ভাঙার জায়গা” অর্থাৎ সবচেয়ে ছোট উপাদানের সূচক (rotation point) বের করা যায় — a[mid]-কে a[hi]-এর সাথে তুলনা করে: a[mid] > a[hi] হলে ভাঙা mid-এর ডানে (lo = mid + 1), নইলে mid বা তার বাঁয়ে (hi = mid). এটি আসলে half-open টেমপ্লেট, predicate “a[i] ≤ a[n − 1]” — যা ভাঙার আগে মিথ্যা, পরে সত্য। rotation point জানলে দুই সাজানো খণ্ডের একটিতে সাধারণ binary search চালানোও আরেকটি সঠিক পদ্ধতি।

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <initializer_list>
using namespace std;

int searchRotated(const vector<int>& a, int x) {   // distinct values; index or -1
    int lo = 0, hi = (int)a.size() - 1;             // closed interval [lo, hi]
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == x) return mid;
        if (a[lo] <= a[mid]) {                      // left part a[lo..mid] is sorted
            if (a[lo] <= x && x < a[mid]) hi = mid - 1; else lo = mid + 1;
        } else {                                    // right part a[mid..hi] is sorted
            if (a[mid] < x && x <= a[hi]) lo = mid + 1; else hi = mid - 1;
        }
    }
    return -1;
}
int minIndex(const vector<int>& a) {               // rotation point
    int lo = 0, hi = (int)a.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] > a[hi]) lo = mid + 1; else hi = mid;
    }
    return lo;
}
int main() {
    vector<int> a = {30, 40, 50, 60, 5, 10, 20};
    cout << "rotation point: " << minIndex(a) << '\n';
    for (int x : {20, 35, 60, 5, 30, 99})
        cout << "search " << setw(2) << x << " -> " << searchRotated(a, x) << '\n';
    vector<int> base = {1, 3, 5, 7, 9, 11, 13}; bool ok = true;  // all rotations
    for (int k = 0; k < (int)base.size(); ++k) {
        vector<int> r = base; rotate(r.begin(), r.begin() + k, r.end());
        for (int x = 0; x < 15; ++x) {
            auto it = find(r.begin(), r.end(), x);  // brute force answer
            int want = it == r.end() ? -1 : int(it - r.begin());
            ok = ok && searchRotated(r, x) == want && r[minIndex(r)] == 1;
        }
    }
    cout << "all 7 rotations checked: " << (ok ? "True" : "False") << '\n';
}

rotation point: 4
search 20 -> 6
search 35 -> -1
search 60 -> 3
search  5 -> 4
search 30 -> 0
search 99 -> -1
all 7 rotations checked: True

def search_rotated(a, x):         # distinct values; index of x or -1
    lo, hi = 0, len(a) - 1        # closed interval [lo, hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x:
            return mid
        if a[lo] <= a[mid]:                  # left part a[lo..mid] is sorted
            if a[lo] <= x < a[mid]: hi = mid - 1
            else:                   lo = mid + 1
        else:                                # right part a[mid..hi] is sorted
            if a[mid] < x <= a[hi]: lo = mid + 1
            else:                   hi = mid - 1
    return -1

def min_index(a):                 # rotation point: index of the smallest
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]: lo = mid + 1      # minimum is right of mid
        else:              hi = mid          # minimum is mid or left of it
    return lo

a = [30, 40, 50, 60, 5, 10, 20]
print("rotation point:", min_index(a))
for x in [20, 35, 60, 5, 30, 99]:
    print(f"search {x:2} -> {search_rotated(a, x)}")

base, ok = [1, 3, 5, 7, 9, 11, 13], True  # every rotation, every x
for k in range(len(base)):
    r = base[k:] + base[:k]
    for x in range(15):
        want = r.index(x) if x in r else -1   # brute force answer
        ok = ok and search_rotated(r, x) == want and r[min_index(r)] == 1
print("all 7 rotations checked:", ok)

rotation point: 4
search 20 -> 6
search 35 -> -1
search 60 -> 3
search  5 -> 4
search 30 -> 0
search 99 -> -1
all 7 rotations checked: True

Peak element — সাজানো নয়, তবু log n

একটি অ্যারেতে peak element হলো এমন ঘর যার মান দুই প্রতিবেশীর চেয়ে বড় (প্রান্তের বাইরের ঘরকে −∞ ধরুন, আর পাশাপাশি দুটি মান সমান নয়)। পাহাড়ি পথে হাঁটছেন: সামনে চড়াই থাকলে সামনে এগোলে একটি চূড়া নিশ্চয়ই পাবেন — কারণ পথ কোথাও না কোথাও আবার নামবে, অথবা শেষ প্রান্তে গিয়ে থামবে, আর সেই প্রান্তও তখন চূড়া।

Pseudocode (0-based; a[-1] = a[n] = -infinity; neighbours differ)

FIND-PEAK(a, n):
    lo = 0, hi = n - 1
    while lo < hi:
        mid = lo + (hi - lo) / 2           // mid + 1 <= hi, so a[mid+1] exists
        if a[mid] < a[mid + 1]: lo = mid + 1   // uphill to the right
        else:                   hi = mid       // downhill: a peak is at mid or left
    return lo

কেন ঠিক? Invariant: “a[lo − 1] < a[lo] (বা lo = 0), আর a[hi] > a[hi + 1] (বা hi = n − 1)”. এই অবস্থায় a[lo..hi]-এর সবচেয়ে বড় মানটি একটি peak: পরিসরের ভেতরের প্রতিবেশীরা তার চেয়ে ছোট, আর প্রান্তে থাকলে invariant বলছে বাইরের প্রতিবেশীও ছোট। a[mid] < a[mid + 1] হলে lo = mid + 1 করলে বাঁ শর্তটি নতুন lo-তে সত্য; নইলে hi = mid করলে ডান শর্তটি সত্য। lo = hi হলে সেই একমাত্র ঘরটিই peak. উদাহরণ [1, 3, 20, 4, 1, 0]: mid = 2, 20 > 4 → hi = 2; mid = 1, 3 < 20 → lo = 2; ফেরত 2 (মান 20). O(log n) — অথচ অ্যারে মোটেও সাজানো নয়! শিক্ষাটি হলো: binary search-এর জন্য দরকার এমন একটি প্রশ্ন, যার উত্তর একটি অর্ধেককে নিরাপদে বাদ দেয়।

৭ · দশমিক সংখ্যায় binary search — বর্গমূল আর নির্দিষ্ট সংখ্যক ঘোরা

এবার অ্যারেই নেই। প্রশ্ন: √2 কত? f(m) = m² ফাংশনটি m ≥ 0-এ বাড়তে থাকে, তাই “m² ≥ 2” একটি monotonic predicate — ছোট m-এ মিথ্যা, বড় m-এ সত্য। সীমানাটিই √2. পূর্ণসংখ্যার সূচকের বদলে এখন একটি বাস্তব সংখ্যার পরিসর [lo, hi] প্রতিবার অর্ধেক করা হয়। গণিতে এর নাম bisection method: f(lo) আর f(hi)-এর চিহ্ন আলাদা আর f অবিচ্ছিন্ন হলে মাঝে একটি মূল আছে (Bolzano-র intermediate value theorem), আর অর্ধেক করতে করতে সেটি ঘিরে ফেলা যায়।

Pseudocode: square root of c >= 0 by bisection on real numbers

SQRT(c):
    lo = 0, hi = max(1, c)          // invariant: lo*lo < c <= hi*hi (or c = 0)
    repeat 100 times:               // a fixed count, NOT "while hi - lo > eps"
        mid = (lo + hi) / 2
        if mid * mid < c: lo = mid
        else:             hi = mid
    return hi

এখানে lo = mid আর hi = mid — mid + 1 নেই, কারণ বাস্তব সংখ্যায় “পরের সংখ্যা” বলে কিছু নেই। নিচে c = 2, শুরুর পরিসর [0, 2]:

পূর্ণসংখ্যার বর্গমূল (⌊√c⌋) চাইলে দশমিকে না গিয়ে half-open টেমপ্লেট দিয়ে “প্রথম m যেখানে m·m > c” খুঁজুন, তারপর এক বাদ দিন — m·m গুণফল long long-এ রাখুন। আর এখানেই পরের পর্বের দরজা: “যে সবচেয়ে ছোট সময়ে কাজটি শেষ করা যায়”, “যে সবচেয়ে বড় দূরত্বে গরু রাখা যায়” — এমন অপ্টিমাইজেশন প্রশ্নকে একটি “এই মান দিয়ে কি সম্ভব?” প্রশ্নে বদলে, সেই হ্যাঁ/না-এর সীমানা binary search দিয়ে খোঁজা। এর নাম উত্তরের ওপর binary search, পুরোটা পর্ব ১৯-এ।

৮ · কত দ্রুত, আর এর চেয়ে দ্রুত সম্ভব কি — বিশ্লেষণ, নিম্নসীমা আর আরও দুই পদ্ধতি

Θ(log n) — হিসাবটি নিখুঁতভাবে

half-open টেমপ্লেটে পরিসরের আকার k = hi − lo. mid = lo + ⌊k/2⌋ হলে বাঁয়ে গেলে নতুন আকার ⌊k/2⌋, ডানে গেলে k − ⌊k/2⌋ − 1 ≤ ⌊k/2⌋. অর্থাৎ প্রতি ঘোরায় আকার সর্বোচ্চ ⌊k/2⌋. n থেকে শুরু করে বারবার অর্ধেক (নিচে গোল) করলে শূন্যে পৌঁছাতে ঠিক ⌊log₂ n⌋ + 1 টি ধাপ লাগে (n ≥ 1). recurrence-এর ভাষায় (পর্ব ০৮): T(n) = T(⌊n/2⌋) + Θ(1), তাই T(n) = Θ(log n).

• lower bound টেমপ্লেট: সমান পেলেও থামে না, তাই best case-ও Θ(log n) — ঘোরার সংখ্যা সবসময় ⌊log₂ n⌋ বা ⌊log₂ n⌋ + 1.
• বন্ধ ছাঁচ (সমান পেলে ফেরত): best case Θ(1) (প্রথম mid-এই x), worst case ⌊log₂ n⌋ + 1 = Θ(log n).
• জায়গা: iterative রূপে O(1); recursive রূপে প্রতিটি ডাক একটি stack frame, গভীরতা Θ(log n), তাই Θ(log n) (পর্ব ০৫)।

Ternary search কি দ্রুত, যেহেতু প্রতিবার তিন ভাগের দুই ভাগ বাদ দেয়? না। প্রতি ধাপে তার দুটি তুলনা লাগে, তাই মোট তুলনা প্রায় 2·log₃ n ≈ 1.26·log₂ n — binary search-এর চেয়ে বেশি। Ternary search-এর আসল ব্যবহার অন্য জায়গায়: একটি চূড়াওয়ালা (unimodal) ফাংশনের সর্বোচ্চ বিন্দু খোঁজা, যেখানে একমুখী predicate সরাসরি নেই।

নিম্নসীমা Ω(log n) — decision tree যুক্তি

কেউ কি আরও চালাক এমন অ্যালগরিদম বানাতে পারেন, যা শুধু উপাদানের তুলনা করে log n-এর চেয়ে কম ধাপে খোঁজে? না — আর এর প্রমাণ সুন্দর। শুধু তুলনা ব্যবহারকারী (comparison-based) যেকোনো অ্যালগরিদমকে একটি decision tree হিসেবে আঁকা যায়: প্রতিটি ভেতরের node একটি প্রশ্ন (“x ≤ a[i]?”), দুটি শাখা দুই উত্তর, আর প্রতিটি পাতা (leaf) একটি চূড়ান্ত উত্তর। একটি নির্দিষ্ট ইনপুটে অ্যালগরিদম মূল থেকে একটি পাতা পর্যন্ত একটি পথ বেয়ে চলে; worst case-এ তুলনার সংখ্যা = গাছের উচ্চতা h. n = 3-এর জন্য lower bound-এর গাছ:

                 x <= a[1] ?
               /            \
            yes              no
       x <= a[0] ?       x <= a[2] ?
        /      \          /      \
     ans 0   ans 1     ans 2   ans 3

lower bound-এর উত্তর 0, 1, …, n — মোট n + 1 টি সম্ভাব্য ফল, আর প্রতিটির জন্য অন্তত একটি পাতা চাই (নইলে কোনো ইনপুটে ভুল উত্তর আসবে)। h উচ্চতার একটি binary tree-তে সর্বোচ্চ 2^h টি পাতা থাকে। তাই

আর binary search ঠিক ⌈log₂(n + 1)⌉ = ⌊log₂ n⌋ + 1 টি তুলনায় কাজ সারে — অর্থাৎ শুধু ক্রমে নয়, ধ্রুবকসহ এটি সর্বোত্তম। এই lower bound কোনো একটি অ্যালগরিদমের নয়, পুরো সমস্যার (পর্ব ০৪)। একই ধাঁচের যুক্তিতে পর্ব ২৪-এ দেখবেন, তুলনা দিয়ে সর্টিং Ω(n log n)-এর নিচে সম্ভব নয়। তবে সীমাটি শুধু তুলনার মডেলে খাটে: hash table (পর্ব ৩২) key-এর ওপর গণিত চালায়, তাই গড়ে O(1); interpolation search মানের পার্থক্য দিয়ে ভাগ করে — নিচে দেখুন।

Exponential (galloping) search — অ্যারের শেষ জানা না থাকলে

ধরুন একটি বিশাল বা অসীম সাজানো ক্রম — একটি log ফাইলের সময়-সাজানো লাইন, যার দৈর্ঘ্য আগে জানা নেই, অথবা খুব লম্বা অ্যারে যেখানে উত্তর সম্ভবত শুরুর কাছে। hi কোথায় শুরু করবেন? Exponential search: সূচক 1, 2, 4, 8, 16, … দেখতে থাকুন, যতক্ষণ না a[b] ≥ x. তখন জানি উত্তর (b/2, b]-এর মধ্যে — সেখানে সাধারণ lower bound.

Pseudocode (0-based): exponential search, answer = first i with a[i] >= x

EXP-SEARCH(a, n, x):                 // n may be huge or unknown (then treat a[i] = +inf past the end)
    if a[0] >= x: return 0
    b = 1
    while b < n and a[b] < x:        // gallop: 1, 2, 4, 8, ...
        b = 2 * b
    return LOWER-BOUND on [b/2 + 1, min(b, n))   // a[b/2] < x is known

উত্তর যদি অবস্থান p-তে থাকে, লাফানোর ধাপ ⌈log₂ p⌉-এর মতো, আর শেষের binary search-ও p/2 আকারের পরিসরে — মোট প্রায় 2·log₂ p টি তুলনা, অর্থাৎ O(log p), n-এর ওপর নির্ভর নয়। Jon Bentley আর Andrew Chi-Chih Yao ১৯৭৬ সালে “An almost optimal algorithm for unbounded searching” প্রবন্ধে অসীম খোঁজার এই প্রশ্ন বিশ্লেষণ করেন। বাস্তবে এর সবচেয়ে বিখ্যাত ব্যবহার Tim Peters-এর ২০০২ সালের Timsort-এ (Python-এর সর্টিং, পর্ব ২৫): দুটি সাজানো খণ্ড জোড়া দেওয়ার সময় একটি খণ্ড থেকে টানা অনেক উপাদান আসতে থাকলে “galloping mode”-এ লাফিয়ে লাফিয়ে সীমানা খোঁজা হয়।

Interpolation search — ফোনবুকে “Zaman” খুঁজতে শেষের দিকে খোলা

ফোনবুকে “Zaman” খুঁজতে কেউ মাঝখানে খোলেন না — সোজা শেষের দিকে যান, কারণ জানেন Z বর্ণমালার শেষে। Interpolation search এই অনুমানটিকে সূত্রে বাঁধে: মান যদি মোটামুটি সমানভাবে ছড়ানো থাকে, তাহলে x-এর সম্ভাব্য অবস্থান

mid-এর বদলে pos দেখে একই ভাবে এক দিক বাদ দেওয়া হয়। W. W. Peterson ১৯৫৭ সালে এর ধারণা প্রকাশ করেন। মান সমভাবে বণ্টিত (uniform) এলোমেলো হলে গড়ে মাত্র O(log log n) টি ধাপ লাগে — ১০০ কোটি উপাদানে মোটামুটি পাঁচ-ছয়টি — যা ১৯৭৬–১৯৭৮ সালে Yao ও Yao এবং Perl, Itai ও Avni-র বিশ্লেষণে প্রতিষ্ঠিত। কিন্তু worst case O(n): [1, 2, 3, …, 99, 10⁹]-এর মতো বাঁকা বণ্টনে pos প্রতিবার মাত্র এক ঘর এগোয়। সাথে আছে গুণফলের overflow আর a[hi] = a[lo] হলে শূন্য দিয়ে ভাগের ঝুঁকি। তাই এটি বিশেষ ক্ষেত্রের (জানা, সমান বণ্টনের সংখ্যাসূচক key) হাতিয়ার; সাধারণ কাজে binary search-ই নিরাপদ।

৯ · AI-এর যুগে binary search — দশ লাইনের কোড, একশো রকম ভুল

“Binary search লিখে দাও” — AI এক সেকেন্ডে লিখবে, আর সাধারণ ক্ষেত্রে প্রায় সবসময় ঠিক। কিন্তু ইন্টারভিউ আর কনটেস্টের প্রশ্ন সাধারণ ক্ষেত্র নয়: “প্রথম অবস্থান”, “শেষ অবস্থান”, “ঠিক বড় এমন প্রথম”, rotated, সদৃশ মান, উত্তরের ওপর খোঁজা। এখানে AI প্রায়ই দুই ছাঁচের লাইন মিশিয়ে ফেলে — while (lo <= hi)-এর সাথে hi = mid — যা কিছু ইনপুটে ঠিক চলে, কিছুতে চিরকাল ঘোরে। ব্যাখ্যাও আত্মবিশ্বাসী থাকে, তাই ভুলটি চোখ এড়িয়ে যায়।

Binary search-এ AI সাধারণত যেসব ভুল করে

AI-এর (বা নিজের) binary search যাচাইয়ের চেকলিস্ট

• কোন ছাঁচ, আর invariant কী — এক বাক্যে লিখেছি; প্রতিটি লাইন সেটির সাথে মিলিয়েছি
• lo <= mid < hi নিশ্চিত, আর প্রতি ঘোরায় পরিসর অন্তত এক কমে — লুপ থামবেই
• এক-ঘর, দুই-ঘর আর সব-সমান অ্যারেতে হাতে dry run করেছি
• ফল n (বা −1) হলে অ্যারের বাইরে পড়া হয় না
• mid = lo + (hi − lo) / 2; দশমিকে নির্দিষ্ট সংখ্যক ঘোরা
• linear search বা bisect/std::lower_bound-এর সাথে random ইনপুটে stress test করেছি