Binary search: সাজানো সারিকে অর্ধেক করতে করতে একটা জায়গায় পৌঁছানো

Amara-র বইয়ের দোকানে 16টা বইয়ের দামের একটা ছাপানো তালিকা আছে, সবচেয়ে সস্তাটা থেকে শুরু। একজন customer জানতে চায়, ঠিক 300 টাকার কোনো বই আছে কি না। আরেকজন জানতে চায়, 310 টাকার একটা নতুন বই তালিকার কোথায় বসবে। সামনে থেকে পড়লে প্রতিটা প্রশ্নে 16 বার পর্যন্ত দেখতে হতে পারে। ছোটদের "বেশি না কম" খেলায় লাগে বড়জোর 5 বার। এই lesson সেই খেলাটাই, শুধু খেলছে library, একটা সাজানো vector-এর উপর।

অনুমানের খেলা: বেশি না কম

Zara 1 থেকে 100-এর মধ্যে একটা পূর্ণসংখ্যা মনে মনে ঠিক করে, আর তুমি অনুমান করো। প্রতিবার ও বলে "বেশি", "কম" নয়তো "হ্যাঁ"। অসাবধান খেলোয়াড় 1 থেকে শুরু করে একটা একটা করে ওঠে, আর তার 100 বার লাগতে পারে। সাবধানী খেলোয়াড় সবসময় বলে, যা এখনো সম্ভব, তার ঠিক মাঝখানের সংখ্যাটা।

প্রথমে বলো 50। Zara "কম" বললে 50 থেকে 100 পর্যন্ত সব সংখ্যা এক উত্তরেই বাদ। বাকি থাকে মোটামুটি 50টা, তারপর 25, তারপর 12, 6, 3 আর 1। তাই সাবধানী খেলোয়াড়ের কখনো 7 বারের বেশি লাগে না, কারণ 7 বার অর্ধেক করলেই 100টা সংখ্যা নেমে আসে একটায়।

Binary search-এর পুরো কথাটা এটাই। যে অংশটা এখনো বাকি, তার মাঝখানের সাথে তুলনা করো, আর যে অর্ধেকে উত্তর থাকতেই পারে না, সেটা ফেলে দাও। "Binary" মানে দুই: প্রতিবার দেখায় বাকি অংশ ভাগ হয় দুই অর্ধেকে। তাই কতবার দেখতে হবে, সেটা বাড়ে n-কে কতবার অর্ধেক করা যায় তার সাথে, n-এর সাথে না।

সাজানো থাকাটাই দাম

খেলাটা চলে, কারণ 1 থেকে 100 সংখ্যাগুলো ক্রমে সাজানো। 50 বলার পরে Zara "কম" বললে তুমি জানো, 50-এর উপরের প্রতিটা সংখ্যাও ভুল। Amara-র তালিকাও একইভাবে কাজ করে, কারণ ওটা ছাপানো হয়েছে সস্তা থেকে দামির দিকে। নিচে ওর 16টা দামের উপর প্রথম 300 খোঁজার কাজটা, lower_bound যেভাবে করে, একবার একবার করে দেখা।

প্রথমবার মাঝখানে পাওয়া গেল 350। সাজানো তালিকায় ওর ডানের সবকিছু 350 বা তার বেশি, তাই প্রথম 300 ওখানে থাকতেই পারে না। সাজানো না হলে একটা 300 যেকোনো জায়গায় লুকিয়ে থাকতে পারত, আর অর্ধেক কেটে দিলে সেটাও ফেলে দেওয়া হতো। তাই সাজানোটাই দাম, একবারই দিতে হয়, আর বদলে প্রতিটা খোঁজা শেষ হয় হাতে গোনা কয়েকবার দেখায়, লম্বা হাঁটা লাগে না।

Library কীভাবে Amara-র তালিকা অর্ধেক করে, দেখো

এই খোঁজাটা C++ library তোমার হয়ে করে দেয়। নিচে Amara-র তালিকায় ওর সবচেয়ে কাজের দুইটা খোঁজা, ধাপে ধাপে। প্রতিটা ধাপে যে অংশটা এখনো বাকি, সেটা লেখা [lo, hi) হিসেবে: index lo ভেতরে, index hi বাইরে। প্রতিবার তুলনা হয় মাঝের element-এর সাথে, যেটা থাকে lo + (hi - lo) / 2-এ। প্রতিটা তুলনা GCC 12-এর library, libstdc++, সত্যিই করেছে; Compiler Explorer-এ একটা run থেকে print করা।

lower_bound চায় প্রথম দামটা, যেটা 300-এর কম না। মাঝের দাম 300-এর কম হলে উত্তর নিশ্চয়ই ওর ডানে। কম না হলে উত্তর ওই index-ই, নয়তো ওর বাঁয়ে। চারবার দেখার পরে আর কিছু বাকি থাকে না, আর bound বসে index 5-এ।

upper_bound চায় প্রথম দামটা, যেটা 300-এর বেশি। প্রথম দুইবার ও একই জায়গা দেখে, তারপর 300-গুলো পেরিয়ে ডানে যেতে থাকে, আর থামে index 8-এ। তাই একই তালিকায় দুই খোঁজা থামে 300-গুলোর দুই মাথায়: ওদের আগে index 5, ওদের পরে index 8।

প্রথম দিনেই যে syntax লাগবে

#include <algorithm>

binary_search(v.begin(), v.end(), x)   true if x is there, false if not
lower_bound(v.begin(), v.end(), x)     the first position whose element is not less than x
upper_bound(v.begin(), v.end(), x)     the first position whose element is greater than x
equal_range(v.begin(), v.end(), x)     both positions at once, as a pair
it - v.begin()                         a position turned into an index
it == v.end()                          the position past the last element: nothing there

তাই একটা খোঁজা উত্তর দেয় "আছে তো?", আর বাকি তিনটা উত্তর দেয় "কোথায়?"।

binary_search বলে হ্যাঁ বা না, এর বেশি কিছু না

binary_search একটাই প্রশ্নের উত্তর দেয়: range-এর কোথাও x-এর সমান কোনো element আছে কি? Print করলে true আসে 1 হয়ে, false আসে 0 হয়ে।

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

int main() {
    vector<int> price{120, 150, 150, 200, 240, 300, 300, 300,
                      350, 420, 450, 480, 520, 600, 640, 700};
    cout << "a book at 300? " << binary_search(price.begin(), price.end(), 300) << '\n';
    cout << "a book at 310? " << binary_search(price.begin(), price.end(), 310) << '\n';
    return 0;
}

a book at 300? 1
a book at 310? 0

300 টাকার বই আছে, 310 টাকার নেই। কিন্তু উত্তর ওখানেই শেষ। 300-টা কোথায়, কয়টা আছে, বা 310 কোথায় বসবে, কিছুই বলে না। নতুনরা জায়গা খুঁজতে binary_search ধরে, অথচ ওর কাছে দেওয়ার মতো কোনো জায়গাই নেই। তাই সাদামাটা হ্যাঁ-না-র জন্য এটা নাও, আর জায়গা চাইলে lower_bound-কে জিজ্ঞেস করো।

lower_bound আর upper_bound: 300-গুলোর দুই পাশে দুইটা বেড়া

ভাবো, পাশাপাশি দুইটা দামের মাঝখানে একটা বেড়া দাঁড় করানো যায়। lower_bound বেড়াটা বসায় প্রথম সেই element-এর ঠিক আগে, যেটা x-এর কম না। upper_bound বসায় শেষ সেই element-এর ঠিক পরে, যেটা x-এর বেশি না। দুই বেড়ার মাঝে থাকে ঠিক x-এর কপিগুলো।

এই যে দুই বেড়া, একটা program হিসেবে। প্রতিটা জায়গা থেকে price.begin() বিয়োগ করে index বানানো হয়েছে, আর program প্রতিটা বেড়ার ঠিক পরের দামটা পড়ে।

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

int main() {
    vector<int> price{120, 150, 150, 200, 240, 300, 300, 300,
                      350, 420, 450, 480, 520, 600, 640, 700};
    auto first = lower_bound(price.begin(), price.end(), 300);
    auto after = upper_bound(price.begin(), price.end(), 300);
    cout << "lower_bound(300): index " << first - price.begin() << ", price " << *first << '\n';
    cout << "upper_bound(300): index " << after - price.begin() << ", price " << *after << '\n';
    cout << "copies of 300: " << after - first << '\n';
    return 0;
}

lower_bound(300): index 5, price 300
upper_bound(300): index 8, price 350
copies of 300: 3

lower_bound থামল index 5-এ, আর ওখানে একটা 300 পেল। upper_bound থামল index 8-এ, 350-এ, শেষ 300-টার এক ঘর পরে। দুইয়ের তফাত 3: 300 টাকার বই তিনটা। তাই x কয়টা আছে, সেটা সবসময় upper বিয়োগ lower। x না থাকলে উত্তর 0, কারণ তখন দুইটা বেড়াই দাঁড়ায় একই ফাঁকে।

equal_range: এক call-এ দুইটা বেড়াই

equal_range দুইটা বেড়া একসাথে ফেরত দেয়, একটা pair হিসেবে: .first হলো lower bound, আর .second upper-টা। Module 1-এর pair এখানে হুবহু একই।

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

int main() {
    vector<int> price{120, 150, 150, 200, 240, 300, 300, 300,
                      350, 420, 450, 480, 520, 600, 640, 700};
    for (int x : {300, 310}) {
        auto range = equal_range(price.begin(), price.end(), x);
        cout << x << " at " << range.first - price.begin() << " to "
             << range.second - price.begin() << ", count "
             << range.second - range.first << '\n';
    }
    return 0;
}

300 at 5 to 8, count 3
310 at 8 to 8, count 0

300-এর জন্য pair-টা ছড়িয়ে আছে index 5 থেকে 8, তিনটা বই। 310-এর জন্য pair-এর দুই অংশই index 8: একটা খালি অংশ, গোনা 0, ঠিক সেই ফাঁকে, যেখানে 310 টাকার বই বসত। তাই equal_range মানে এক call-এ lower_bound আর upper_bound, আর ওর তুলনাগুলো গুনবে lesson 02।

জায়গা থেকে index, আর end() check

জায়গা হলো একটা iterator, কোনো সংখ্যা না। Vector-এ it - v.begin() ওকে index বানায়: ওর আগে কয়টা element আছে। প্রতিটা element x-এর কম হলে lower_bound ফেরত দেয় v.end(), শেষ element-এর পরের জায়গা। ওখানে কোনো element নেই, তাই *it পড়ার আগে v.end()-এর সাথে মিলিয়ে নাও।

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

int main() {
    vector<int> price{120, 150, 150, 200, 240, 300, 300, 300,
                      350, 420, 450, 480, 520, 600, 640, 700};
    for (int x : {310, 100, 800}) {
        auto it = lower_bound(price.begin(), price.end(), x);
        int index = it - price.begin();
        if (it == price.end()) {
            cout << x << ": nothing costs that much; it goes last, at index " << index << '\n';
        } else {
            cout << x << ": goes at index " << index << ", before the " << *it << "-taka book\n";
        }
    }
    return 0;
}

310: goes at index 8, before the 350-taka book
100: goes at index 0, before the 120-taka book
800: nothing costs that much; it goes last, at index 16

310 টাকার বই বসবে index 8-এ, 300-গুলো আর 350-এর মাঝখানে। 100 টাকার বই বসত সবার আগে। তালিকায় 800 বা তার বেশি দামের কিছুই নেই, তাই lower_bound ফেরত দিল end(), আর index 16 হলো তালিকার size। তাই জায়গার বেলায় C++-এর "পাওয়া যায়নি" হলো end(), যেখানে অন্য অনেক ভাষা -1 ব্যবহার করে।

খরচ কত: O(log n)

প্রতিবার দেখায় বাকি অংশ অর্ধেক হয়। তাই কতবার দেখতে হবে, সেটা মোটামুটি n-কে কতবার অর্ধেক করলে একটা জায়গা বাকি থাকে, তত। সেই সংখ্যাটা হলো n-এর base-2 logarithm, লেখা হয় log n। খরচটা O(log n), পড়ে "order log n"। সামনে থেকে পড়া মানে O(n): সবচেয়ে খারাপ বেলায় প্রতিটা element একবার করে।

Table-এ আছে GCC 12-এর lower_bound সত্যিই কয়টা তুলনা করেছে। একটা গোনার comparator -1 থেকে 2n পর্যন্ত প্রতিটা x খুঁজেছে, 0, 2, 4, এভাবে ভরা vector-এ। গোনাগুলো এসেছে Compiler Explorer-এ একটা run থেকে, GCC 12.2, g++ -O2 -std=c++17, আর একই input সবসময় একই গোনা দেয়।

দশ লাখ দামের জন্য বড়জোর 20টা তুলনা লাগে, কারণ 20টা 2 পরপর গুণ করলে হয় 1048576। তালিকা হাজার গুণ লম্বা করায় তুলনা বাড়ল মাত্র 10টার মতো। তাই range সাজানো থাকলে binary search লম্বা হাঁটাকে বানিয়ে দেয় ছোট্ট কয়েকটা লাফ।

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

int main() {
    vector<int> route{3, 8, 11, 17, 24, 31, 40};   // already sorted
    for (int r : {17, 18, 3, 41}) {
        bool stops = binary_search(route.begin(), route.end(), r);
        cout << "route " << r << ": " << (stops ? "stops here" : "does not stop") << '\n';
    }
    return 0;
}

route 17: stops here
route 18: does not stop
route 3: stops here
route 41: does not stop

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

int main() {
    vector<int> temp{18, 21, 21, 21, 24, 26, 26, 30};   // a week of readings, sorted
    for (int x : {21, 26, 25}) {
        int lo = lower_bound(temp.begin(), temp.end(), x) - temp.begin();
        int hi = upper_bound(temp.begin(), temp.end(), x) - temp.begin();
        cout << x << ": lower " << lo << ", upper " << hi << ", copies " << hi - lo << '\n';
    }
    return 0;
}

21: lower 1, upper 4, copies 3
26: lower 5, upper 7, copies 2
25: lower 5, upper 5, copies 0

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    vector<string> words{"anchor", "bridge", "candle", "garden", "island",
                         "lantern", "meadow", "puzzle", "rocket", "violin"};
    for (string w : {"garden", "gardens", "harbor", "zebra"}) {
        if (binary_search(words.begin(), words.end(), w)) {
            cout << w << ": on the list\n";
        } else {
            auto it = lower_bound(words.begin(), words.end(), w);
            cout << w << ": not there; it would go at index " << it - words.begin();
            if (it != words.end()) {
                cout << ", before " << *it;
            }
            cout << '\n';
        }
    }
    return 0;
}

garden: on the list
gardens: not there; it would go at index 4, before island
harbor: not there; it would go at index 4, before island
zebra: not there; it would go at index 10

vector<int> cleaned{204, 211, 207, 202, 215, 209};   // in the order Alice cleaned them
for (int room : {207, 202, 215, 211}) {
    cout << room << ": " << (binary_search(cleaned.begin(), cleaned.end(), room) ? "cleaned" : "not yet") << '\n';
}

vector<int> price{120, 150, 200, 300, 350};
if (lower_bound(price.begin(), price.end(), 310) == -1) {
    cout << "no such book\n";
}

vector<int> price{120, 150, 200, 300, 350};
auto it = lower_bound(price.begin(), price.end(), 800);
cout << "index " << it - price.begin() << '\n';
cout << "price " << *it << '\n';

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> price{120, 150, 200, 300, 350};
    cout << lower_bound(price.begin(), price.end(), 300) - price.begin() << '\n';
    cout << upper_bound(price.begin(), price.end(), 300) - price.begin() << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 0;
    cin >> n;
    vector<int> tags(n);   // the tags in the order the items were found
    for (int i = 0; i < n; i++) {
        cin >> tags[i];
    }
    // Get tags ready for a binary search, once.

    int q = 0;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int ticket = 0;
        cin >> ticket;
        // Print yes if an item with this tag is at the desk, no if not.
    }
    return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> leaves(n);   // departure times in minutes after midnight, sorted
    for (int i = 0; i < n; i++) {
        cin >> leaves[i];
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        // Print how many minutes Alice waits for the next bus. If no bus
        // leaves at t or later today, she waits for the first bus tomorrow.
    }
    return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<long long> amara(n);   // Amara's prices, sorted
    for (int i = 0; i < n; i++) {
        cin >> amara[i];
    }
    int m;
    cin >> m;
    vector<long long> bob(m);   // Bob's prices, sorted
    for (int i = 0; i < m; i++) {
        cin >> bob[i];
    }

    // Find the smallest difference between one of Amara's prices and one
    // of Bob's, and print it.

    return 0;
}

এরপর lesson 02 চারটা call-এর প্রতিটা রূপ দেখাবে, একটা একটা করে, প্রতিটার খরচ আর ফাঁদসহ।