پرش به محتویات

جستجوی دودویی

جستجوی دودویی (Binary search) روشی است که با تقسیم بازه‌ی جستجو به دو قسمت، امکان جستجوی سریع‌تر را فراهم می‌کند. رایج‌ترین کاربرد آن جستجوی مقادیر در آرایه‌های مرتب است، اما ایده‌ی تقسیم کردن در بسیاری از وظایف رایج دیگر نیز حیاتی است.

جستجو در آرایه‌های مرتب

معمولی‌ترین مسئله‌ای که به جستجوی دودویی منجر می‌شود، به این صورت است. به شما یک آرایه مرتب $A_0 \leq A_1 \leq \dots \leq A_{n-1}$ داده می‌شود، و شما باید بررسی کنید که آیا $k$ در این دنباله وجود دارد یا نه. ساده‌ترین راه‌حل این است که هر عنصر را تک به تک بررسی کرده و با $k$ مقایسه کنیم (که به آن جستجوی خطی می‌گویند). این رویکرد در زمان $O(n)$ کار می‌کند، اما از این واقعیت که آرایه مرتب است، استفاده نمی‌کند.


جستجوی دودویی برای مقدار $7$ در یک آرایه.
این تصویر اثر [AlwaysAngry](https://commons.wikimedia.org/wiki/User:AlwaysAngry) تحت مجوز CC BY-SA 4.0 منتشر شده است.

حالا فرض کنید دو اندیس $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]$ انتخاب کرده و بازه را به دو نیم تقسیم کنیم. بنابراین، بازه‌ی فعال در هر مرحله نصف می‌شود تا به اندازه ۱ برسد. پس، اگر فرآیند به $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$ شما باید برای جستجوی خطی تقریباً یک میلیون عملیات انجام دهید، اما با جستجوی دودویی تنها حدود ۲۰ عملیات نیاز است.

حد پایین و حد بالا

اغلب راحت‌تر است که به جای موقعیت دقیق عنصر، موقعیت اولین عنصری که بزرگتر یا مساوی $k$ است (که به آن حد پایین یا lower bound $k$ در آرایه گفته می‌شود) یا موقعیت اولین عنصری که بزرگتر از $k$ است (که به آن حد بالا یا upper bound $k$ گفته می‌شود) را پیدا کنیم.

حد پایین و حد بالا با هم، یک نیم‌بازه (احتمالاً تهی) از عناصر آرایه را که برابر با $k$ هستند، مشخص می‌کنند. برای بررسی وجود $k$ در آرایه، کافی است حد پایین آن را پیدا کرده و بررسی کنیم که آیا عنصر متناظر با آن برابر با $k$ است یا خیر.

پیاده‌سازی

توضیحات بالا شرحی کلی از الگوریتم ارائه می‌دهد. برای جزئیات پیاده‌سازی، باید دقیق‌تر باشیم.

ما یک جفت $L < R$ را به گونه‌ای نگه می‌داریم که $A_L \leq k < A_R$. به این معنی که بازه‌ی جستجوی فعال $[L, R)$ است. در اینجا از نیم‌بازه به جای بازه‌ی بسته $[L, R]$ استفاده می‌کنیم، زیرا مشخص شده که به کار کمتری برای مدیریت حالت‌های خاص (corner case) نیاز دارد.

وقتی $R = L+1$ باشد، از تعاریف بالا می‌توان نتیجه گرفت که $R$ حد بالای $k$ است. بهتر است $R$ را با اندیس پس از پایان، یعنی $R=n$، و $L$ را با اندیس پیش از شروع، یعنی $L=-1$، مقداردهی اولیه کنیم. این کار تا زمانی که مقادیر $A_L$ و $A_R$ را مستقیماً در الگوریتم خود ارزیابی نکنیم، مشکلی ایجاد نمی‌کند و به طور رسمی آن‌ها را به عنوان $A_L = -\infty$ و $A_R = +\infty$ در نظر می‌گیریم.

در نهایت، برای مشخص کردن مقدار $M$ که انتخاب می‌کنیم، ما از $M = \lfloor \frac{L+R}{2} \rfloor$ استفاده خواهیم کرد.

در این صورت پیاده‌سازی می‌تواند به این شکل باشد:

// ... یک آرایه مرتب به صورت 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 دو عدد صحیح مثبت بزرگ باشند، منجر به سرریز (overflow) شود، و این خطا همانطور که در این پست وبلاگ توضیح داده شده، حدود ۹ سال در 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). $$

جستجوی دودویی، به شکلی که در بالا توضیح داده شد، افراز (partition) آرایه را بر اساس گزاره $f(M)$ پیدا می‌کند، که در آنجا مقدار بولی عبارت $k < A_M$ را نگه می‌دارد. امکان استفاده از هر گزاره یکنوا دلخواه به جای $k < A_M$ وجود دارد. این موضوع به ویژه زمانی مفید است که محاسبه $f(k)$ برای هر مقدار ممکن، زمان زیادی ببرد. به عبارت دیگر، جستجوی دودویی اندیس منحصر به فرد $L$ را به طوری که $f(L) = 0$ و $f(R)=f(L+1)=1$ باشد، در صورت وجود چنین نقطه گذاری، پیدا می‌کند، یا اگر $f(0) = \dots = f(n-1) = 0$ باشد $L = n-1$ را به ما می‌دهد و یا اگر $f(0) = \dots = f(n-1) = 1$ باشد $L = -1$ را نتیجه می‌دهد.

اثبات صحت با فرض وجود یک نقطه گذار، یعنی $f(0)=0$ و $f(n-1)=1$: پیاده‌سازی ناوردای حلقه (loop invariant) $f(l)=0, f(r)=1$ را حفظ می‌کند. وقتی $r - l > 1$ باشد، انتخاب $m$ به این معنی است که $r-l$ همیشه کاهش می‌یابد. حلقه زمانی خاتمه می‌یابد که $r - l = 1$ شود و نقطه گذار مورد نظر ما را به دست می‌دهد.

// ... f(i) یک تابع بولی است به طوری که 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$ و با جمع غیرمنفی وجود دارد یا خیر، که این کار با استفاده از مجموع‌های پیشوندی (prefix sums) قابل انجام است.

جستجوی پیوسته

فرض کنید $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$. توجه داشته باشید که برخلاف پاراگراف‌های قبلی، لازم نیست که تابع یکنوا باشد.

مقدار $x$ را می‌توان با دقت $\pm\delta$ در زمان $O\left(\log \frac{R-L}{\delta}\right)$ برای هر مقدار مشخصی از $\delta$ تقریب زد. ایده اساساً همان است، اگر $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$ یک واحد کاهش می‌یابد.

این الگو به طور گسترده در مسائل مربوط به درخت‌ها، مانند یافتن کوچکترین جد مشترک (lowest common ancestor) دو رأس یا یافتن جد یک رأس خاص با ارتفاع معین، استفاده می‌شود. همچنین می‌توان آن را برای مثال برای یافتن $k$-امین عنصر غیرصفر در یک درخت فنویک (Fenwick tree) تطبیق داد.

مسائل تمرینی