বাইনারি সার্চ#

বাইনারি সার্চ হলো এমন একটি পদ্ধতি যা সার্চ ইন্টারভালকে দুই ভাগে ভাগ করে দ্রুত কিছু খুঁজে বের করতে সাহায্য করে। এর সবচেয়ে সাধারণ ব্যবহার হলো সর্টেড অ্যারেতে মান খোঁজা, তবে এই ভাগ করার ধারণাটি আরও অনেক আদর্শ সমস্যায় অত্যন্ত গুরুত্বপূর্ণ।

সর্টেড অ্যারেতে সার্চ#

সবচেয়ে আদর্শ সমস্যা যা বাইনারি সার্চের দিকে নিয়ে যায় তা হলো নিম্নরূপ। আপনাকে একটি সর্টেড অ্যারে $A_0 \leq A_1 \leq \dots \leq A_{n-1}$ দেওয়া আছে, পরীক্ষা করুন $k$ এই ক্রমের মধ্যে আছে কিনা। সবচেয়ে সরল সমাধান হলো প্রতিটি উপাদান একে একে যাচাই করে $k$-এর সাথে তুলনা করা (একে লিনিয়ার সার্চ বলা হয়)। এই পদ্ধতি $O(n)$-এ কাজ করে, কিন্তু অ্যারে যে সর্টেড সেই তথ্যটি কাজে লাগায় না।


একটি অ্যারেতে $7$ মানের বাইনারি সার্চ।
The image by AlwaysAngry is distributed under CC BY-SA 4.0 license.

এখন ধরি আমরা দুটি ইনডেক্স $L < R$ জানি যেন $A_L \leq k \leq A_R$। যেহেতু অ্যারে সর্টেড, আমরা অনুমান করতে পারি যে $k$ হয় $A_L, A_{L+1}, \dots, A_R$-এর মধ্যে আছে, অথবা অ্যারেতে একদমই নেই। যদি আমরা এমন একটি যেকোনো ইনডেক্স $M$ নিই যেন $L < M < R$ এবং $k$, $A_M$-এর চেয়ে ছোট না বড় তা পরীক্ষা করি। দুটি সম্ভাব্য ক্ষেত্র আছে:

  1. $A_L \leq k \leq A_M$। এই ক্ষেত্রে, আমরা সমস্যাটি $[L, R]$ থেকে $[L, M]$-এ কমিয়ে আনি;
  2. $A_M \leq k \leq A_R$। এই ক্ষেত্রে, আমরা সমস্যাটি $[L, R]$ থেকে $[M, R]$-এ কমিয়ে আনি।

যখন $M$ নেওয়া সম্ভব হয় না, অর্থাৎ যখন $R = L + 1$, তখন আমরা সরাসরি $k$-কে $A_L$ এবং $A_R$-এর সাথে তুলনা করি। অন্যথায় আমরা $M$ এমনভাবে বাছাই করতে চাই যেন সবচেয়ে খারাপ ক্ষেত্রে এটি সক্রিয় সেগমেন্টকে যত দ্রুত সম্ভব একটি মাত্র উপাদানে কমিয়ে আনে।

যেহেতু সবচেয়ে খারাপ ক্ষেত্রে আমরা সবসময় $[L, M]$ এবং $[M, R]$-এর বড়টিতে কমে আসব। সুতরাং, সবচেয়ে খারাপ ক্ষেত্রে হ্রাস হবে $R-L$ থেকে $\max(M-L, R-M)$-এ। এই মানটি ন্যূনতম করতে আমাদের $M \approx \frac{L+R}{2}$ নেওয়া উচিত, তখন

$$ M-L \approx \frac{R-L}{2} \approx R-M. $$

অন্যভাবে বলতে গেলে, সবচেয়ে খারাপ ক্ষেত্রের দৃষ্টিকোণ থেকে সবসময় $M$-কে $[L, R]$-এর মাঝখানে নিয়ে অর্ধেক ভাগ করাই সর্বোত্তম। এভাবে সক্রিয় সেগমেন্ট প্রতিটি ধাপে অর্ধেক হতে থাকে যতক্ষণ না এটি আকার $1$ হয়। সুতরাং, যদি প্রক্রিয়াটিতে $h$ ধাপ লাগে, শেষ পর্যন্ত এটি $R$ ও $L$-এর পার্থক্য $R-L$ থেকে $\frac{R-L}{2^h} \approx 1$-এ কমিয়ে আনে, যেখান থেকে আমরা সমীকরণ পাই $2^h \approx R-L$।

উভয় পক্ষে $\log_2$ নিলে আমরা পাই $h \approx \log_2(R-L) \in O(\log n)$।

লগারিদমিক সংখ্যক ধাপ লিনিয়ার সার্চের তুলনায় অনেক বেশি কার্যকর। উদাহরণস্বরূপ, $n \approx 2^{20} \approx 10^6$ হলে লিনিয়ার সার্চে প্রায় দশ লক্ষ অপারেশন লাগবে, কিন্তু বাইনারি সার্চে লাগবে মাত্র প্রায় $20$টি অপারেশন।

লোয়ার বাউন্ড এবং আপার বাউন্ড#

প্রায়ই $k$-এর সঠিক অবস্থান খোঁজার বদলে প্রথম যে উপাদানটি $k$-এর সমান বা বড় সেটির অবস্থান (অ্যারেতে $k$-এর লোয়ার বাউন্ড) অথবা প্রথম যে উপাদানটি $k$-এর চেয়ে বড় সেটির অবস্থান ($k$-এর আপার বাউন্ড) খোঁজা সুবিধাজনক।

একসাথে, লোয়ার বাউন্ড ও আপার বাউন্ড অ্যারের উপাদানগুলোর একটি সম্ভবত খালি হাফ-ইন্টারভাল তৈরি করে যেগুলো $k$-এর সমান। অ্যারেতে $k$ আছে কিনা তা পরীক্ষা করতে এর লোয়ার বাউন্ড খুঁজে বের করে সংশ্লিষ্ট উপাদানটি $k$-এর সমান কিনা দেখলেই যথেষ্ট।

ইমপ্লিমেন্টেশন#

উপরের ব্যাখ্যাটি অ্যালগরিদমের একটি মোটামুটি বর্ণনা দেয়। ইমপ্লিমেন্টেশনের বিস্তারিতের জন্য আমাদের আরও সুনির্দিষ্ট হতে হবে।

আমরা এমন একটি জোড়া $L < R$ বজায় রাখব যেন $A_L \leq k < A_R$। অর্থাৎ সক্রিয় সার্চ ইন্টারভাল হলো $[L, R)$। এখানে সেগমেন্ট $[L, R]$-এর বদলে হাফ-ইন্টারভাল ব্যবহার করা হয়েছে কারণ এতে কর্নার কেস কম হয়।

যখন $R = L+1$, তখন উপরের সংজ্ঞা থেকে আমরা বলতে পারি যে $R$ হলো $k$-এর আপার বাউন্ড। $R$-কে past-the-end ইনডেক্স, অর্থাৎ $R=n$, এবং $L$-কে before-the-beginning ইনডেক্স, অর্থাৎ $L=-1$ দিয়ে ইনিশিয়ালাইজ করা সুবিধাজনক। আমাদের অ্যালগরিদমে যতক্ষণ আমরা সরাসরি $A_L$ এবং $A_R$ ইভ্যালুয়েট না করি ততক্ষণ এটি ঠিক আছে, আনুষ্ঠানিকভাবে $A_L = -\infty$ এবং $A_R = +\infty$ ধরে নেওয়া যায়।

পরিশেষে, আমরা $M$-এর যে মান নেব সে বিষয়ে সুনির্দিষ্ট হতে, আমরা $M = \lfloor \frac{L+R}{2} \rfloor$ ব্যবহার করব।

তাহলে ইমপ্লিমেন্টেশনটি এরকম হতে পারে:

... // a sorted array is stored as a[0], a[1], ..., a[n-1]
int l = -1, r = n;
while (r - l > 1) {
    int m = (l + r) / 2;
    if (k < a[m]) {
        r = m; // a[l] <= k < a[m] <= a[r]
    } else {
        l = m; // a[l] <= a[m] <= k < a[r]
    }
}

অ্যালগরিদম চলাকালীন আমরা কখনো $A_L$ বা $A_R$ ইভ্যালুয়েট করি না, কারণ $L < M < R$। শেষে, $L$ হবে শেষ উপাদানটির ইনডেক্স যেটি $k$-এর চেয়ে বড় নয় (অথবা $-1$ যদি এমন কোনো উপাদান না থাকে) এবং $R$ হবে $k$-এর চেয়ে বড় প্রথম উপাদানটির ইনডেক্স (অথবা $n$ যদি এমন কোনো উপাদান না থাকে)।

দ্রষ্টব্য। m-কে m = (r + l) / 2 হিসেবে হিসাব করলে ওভারফ্লো হতে পারে যদি l এবং r দুটি পজিটিভ ইন্টিজার হয়, এবং এই বাগটি প্রায় ৯ বছর JDK-তে ছিল যা এই ব্লগপোস্টে বর্ণিত হয়েছে। কিছু বিকল্প পদ্ধতির মধ্যে রয়েছে যেমন m = l + (r - l) / 2 লেখা যা পজিটিভ ইন্টিজার l ও r-এর জন্য সবসময় কাজ করে, কিন্তু l নেগেটিভ হলে এখনও ওভারফ্লো হতে পারে। আপনি যদি C++20 ব্যবহার করেন, তাহলে m = std::midpoint(l, r) আকারে একটি বিকল্প সমাধান পাওয়া যায় যা সবসময় সঠিকভাবে কাজ করে।

যেকোনো প্রেডিকেটে সার্চ#

ধরি $f : \{0,1,\dots, n-1\} \to \{0, 1\}$ হলো $0,1,\dots,n-1$-এ সংজ্ঞায়িত একটি বুলিয়ান ফাংশন যা মনোটনিকভাবে বর্ধমান, অর্থাৎ

$$ f(0) \leq f(1) \leq \dots \leq f(n-1). $$

বাইনারি সার্চ, যেভাবে উপরে বর্ণনা করা হয়েছে, প্রেডিকেট $f(M)$ দ্বারা অ্যারের পার্টিশন খুঁজে বের করে, যেখানে $k < A_M$ এক্সপ্রেশনের বুলিয়ান মান ধারণ করে। $k < A_M$-এর বদলে যেকোনো মনোটনিক প্রেডিকেট ব্যবহার করা সম্ভব। এটি বিশেষভাবে উপযোগী যখন $f(k)$-এর হিসাব করতে এত বেশি সময় লাগে যে প্রতিটি সম্ভাব্য মানের জন্য এটি গণনা করা ব্যবহারিক নয়। অন্যভাবে বলতে গেলে, বাইনারি সার্চ এমন একটি অনন্য ইনডেক্স $L$ খুঁজে বের করে যেন $f(L) = 0$ এবং $f(R)=f(L+1)=1$ যদি এমন কোনো ট্রানজিশন পয়েন্ট থাকে, অথবা $L = n-1$ দেয় যদি $f(0) = \dots = f(n-1) = 0$ হয় অথবা $L = -1$ দেয় যদি $f(0) = \dots = f(n-1) = 1$ হয়।

ট্রানজিশন পয়েন্ট আছে ধরে নিয়ে সঠিকতার প্রমাণ, অর্থাৎ $f(0)=0$ এবং $f(n-1)=1$: ইমপ্লিমেন্টেশনটি লুপ ইনভ্যারিয়েন্ট $f(l)=0, f(r)=1$ বজায় রাখে। যখন $r - l > 1$, $m$-এর বাছাই নিশ্চিত করে যে $r-l$ সবসময় কমবে। লুপটি $r - l = 1$ হলে শেষ হয়, যা আমাদের কাঙ্ক্ষিত ট্রানজিশন পয়েন্ট দেয়।

... // f(i) is a boolean function such that f(0) <= ... <= f(n-1)
int l = -1, r = n;
while (r - l > 1) {
    int m = (l + r) / 2;
    if (f(m)) {
        r = m; // 0 = f(l) < f(m) = 1
    } else {
        l = m; // 0 = f(m) < f(r) = 1
    }
}

বাইনারি সার্চ অন দ্য আনসার#

এই পরিস্থিতি প্রায়ই দেখা যায় যখন আমাদের কোনো মান গণনা করতে বলা হয়, কিন্তু আমরা কেবল পরীক্ষা করতে পারি এই মানটি কমপক্ষে $i$ কিনা। উদাহরণস্বরূপ, আপনাকে একটি অ্যারে $a_1,\dots,a_n$ দেওয়া আছে এবং আপনাকে সর্বোচ্চ ফ্লোরড গড় যোগফল খুঁজে বের করতে বলা হয়েছে

$$ \left \lfloor \frac{a_l + a_{l+1} + \dots + a_r}{r-l+1} \right\rfloor $$

$l,r$-এর সব সম্ভাব্য জোড়ার মধ্যে যেখানে $r-l \geq x$। এই সমস্যাটি সমাধান করার একটি সহজ উপায় হলো পরীক্ষা করা উত্তরটি কমপক্ষে $\lambda$ কিনা, অর্থাৎ এমন কোনো জোড়া $l, r$ আছে কিনা যেন নিচেরটি সত্য হয়:

$$ \frac{a_l + a_{l+1} + \dots + a_r}{r-l+1} \geq \lambda. $$

সমতুল্যভাবে, এটি পুনর্লিখন করা যায়

$$ (a_l - \lambda) + (a_{l+1} - \lambda) + \dots + (a_r - \lambda) \geq 0, $$

তাহলে এখন আমাদের পরীক্ষা করতে হবে নতুন অ্যারে $a_i - \lambda$-এর কমপক্ষে $x+1$ দৈর্ঘ্যের এমন কোনো সাবঅ্যারে আছে কিনা যার যোগফল অঋণাত্মক, যা কিছু প্রিফিক্স সাম দিয়ে করা সম্ভব।

কন্টিনিউয়াস সার্চ#

ধরি $f : \mathbb R \to \mathbb R$ হলো একটি বাস্তব-মানের ফাংশন যা $[L, R]$ সেগমেন্টে কন্টিনিউয়াস।

সাধারণতা না হারিয়ে ধরি $f(L) \leq f(R)$। মধ্যবর্তী মান উপপাদ্য থেকে বলা যায় যে যেকোনো $y \in [f(L), f(R)]$-এর জন্য এমন $x \in [L, R]$ আছে যেন $f(x) = y$। লক্ষ্য করুন, পূর্ববর্তী অনুচ্ছেদগুলোর বিপরীতে, ফাংশনটি মনোটনিক হওয়ার প্রয়োজন নেই।

যেকোনো নির্দিষ্ট $\delta$-এর জন্য $x$-এর মান $\pm\delta$ পর্যন্ত সূক্ষ্মভাবে $O\left(\log \frac{R-L}{\delta}\right)$ সময়ে নির্ণয় করা যায়। ধারণাটি মূলত একই, যদি আমরা $M \in (L, R)$ নিই তাহলে $f(M)$, $y$-এর চেয়ে বড় কিনা তার ওপর ভিত্তি করে সার্চ ইন্টারভাল $[L, M]$ অথবা $[M, R]$-এ কমাতে পারব। এখানে একটি সাধারণ উদাহরণ হলো বিজোড়-ডিগ্রি বহুপদীর মূল খোঁজা।

উদাহরণস্বরূপ, ধরি $f(x)=x^3 + ax^2 + bx + c$। তাহলে $L \to -\infty$ এবং $R \to +\infty$ হলে $f(L) \to -\infty$ এবং $f(R) \to +\infty$ হয়। এর অর্থ হলো সবসময় যথেষ্ট ছোট $L$ এবং যথেষ্ট বড় $R$ পাওয়া সম্ভব যেন $f(L) < 0$ এবং $f(R) > 0$ হয়। তারপর, বাইনারি সার্চ দিয়ে ইচ্ছামতো ছোট ইন্টারভাল খুঁজে বের করা সম্ভব যেখানে এমন $x$ আছে যেন $f(x)=0$।

২-এর পাওয়ার দিয়ে সার্চ#

বাইনারি সার্চ করার আরেকটি উল্লেখযোগ্য উপায় হলো, একটি সক্রিয় সেগমেন্ট বজায় রাখার বদলে, বর্তমান পয়েন্টার $i$ এবং বর্তমান পাওয়ার $k$ বজায় রাখা। পয়েন্টার $i=L$ থেকে শুরু হয় এবং তারপর প্রতিটি ইটারেশনে $i+2^k$ বিন্দুতে প্রেডিকেট পরীক্ষা করা হয়। যদি প্রেডিকেট এখনও $0$ থাকে, তাহলে পয়েন্টার $i$ থেকে $i+2^k$-এ এগিয়ে যায়, অন্যথায় এটি একই থাকে, তারপর পাওয়ার $k$ ১ কমানো হয়।

এই পদ্ধতি ট্রি-সম্পর্কিত সমস্যায় ব্যাপকভাবে ব্যবহৃত হয়, যেমন দুটি ভার্টেক্সের লোয়েস্ট কমন অ্যানসেস্টর খোঁজা অথবা একটি নির্দিষ্ট ভার্টেক্সের এমন পূর্বপুরুষ খোঁজা যার একটি নির্দিষ্ট উচ্চতা আছে। এটি ফেনউইক ট্রি-তে $k$-তম নন-জিরো উপাদান খোঁজার মতো কাজেও ব্যবহার করা যায়।

অনুশীলন সমস্যা#