جست‌وجوی دودویی بدون باگ‌های یکی‌کم‌ویکی‌زیاد

جست‌وجوی دودویی (binary search) در یک جمله خلاصه می‌شود: به آیتمِ وسط نگاه کن، بعد نیمه‌ای را که نمی‌تواند چیزِ موردنظرت را داشته باشد دور بریز. هر مرحله بازهٔ باقی‌مانده را نصف می‌کند؛ پس حتی یک میلیارد آیتمِ مرتب فقط حدود ۳۰ مرحله لازم دارد. این یعنی O(log n)؛ اگر Big-O برایتان تازه است، از نماد Big-O با کد واقعی شروع کنید.

درست نوشتنش اما داستان دیگری است. جان بنتلی در کتاب Programming Pearls می‌گوید وقتی از برنامه‌نویس‌های حرفه‌ای خواست جست‌وجوی دودویی بنویسند، حدود ۹۰ درصدشان باگ داشتند. نسخهٔ کتابخانهٔ استاندارد جاوا هم یک باگ سرریز (overflow) داشت که حدود نُه سال کسی متوجهش نشد. مقصرهای همیشگی خطاهای یکی‌کم‌ویکی‌زیاد (off-by-one) هستند: < یا <=؟ mid یا mid + 1؟ حلقه کِی تمام می‌شود؟

این مقاله یک الگو به شما می‌دهد که جواب این سؤال‌ها را خودش می‌دهد، و نشان می‌دهد تا کجا می‌شود از آن استفاده کرد.

سؤالی که باید پرسید#

«آیا x در لیست هست؟» ضعیف‌ترین شکلِ جست‌وجوی دودویی است. سؤالِ بسیار مفیدتر این است:

اولین آیتمی که بزرگ‌تر یا مساوی x است کجاست؟

به این معمولاً کران پایین (lower bound) می‌گویند. چند سؤال را هم‌زمان جواب می‌دهد: آیا x وجود دارد، اگر چند بار تکرار شده از کجا شروع می‌شود، و برای مرتب ماندنِ لیست باید کجا درج شود.

یک الگو: بازهٔ نیمه‌باز#

def lower_bound(a, x):
    """Index of the first item >= x, or len(a) if every item is smaller."""
    lo, hi = 0, len(a)            # invariant: the answer is between lo and hi (inclusive)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1          # a[mid] is too small, so the answer is to its right
        else:
            hi = mid              # a[mid] could be the answer: keep it in range
    return lo

هر خط از ناوردا (invariant) نتیجه می‌شود؛ همان جمله‌ای که در کامنت آمده و در تمام اجرای حلقه درست می‌ماند:

• hi از len(a) شروع می‌شود، نه len(a) - 1، چون «هیچ آیتمی به اندازهٔ کافی بزرگ نیست» هم جوابِ معتبری است.
• اگر a[mid] < x باشد، mid و همهٔ آیتم‌های قبل از آن کوچک‌اند؛ پس جواب دست‌کم mid + 1 است.
• در غیر این صورت a[mid] >= x است، پس mid ممکن است جواب باشد. نمی‌توانیم از آن بگذریم؛ پس hi = mid، نه mid - 1.
• بازه در هر دور کوچک‌تر می‌شود (mid همیشه از hi کمتر است)، پس حلقه تمام می‌شود. وقتی lo == hi شد، فقط یک نامزد باقی مانده و همان جواب است.

بیایید جست‌وجوی 23 را دنبال کنیم:

a = [3, 8, 12, 15, 23, 23, 31, 42, 56, 70]
lower_bound(a, 23)   # 4  (the first 23)
lower_bound(a, 20)   # 4  (20 would be inserted before the first 23)
lower_bound(a, 99)   # 10 (bigger than everything: len(a))
lower_bound(a, 1)    # 0

حالا بررسیِ عضویت یک خط است، بدون هیچ حالت خاصی داخل حلقه:

def contains(a, x):
    i = lower_bound(a, x)
    return i < len(a) and a[i] == x

کران بالا و شمارش#

< را به <= تغییر دهید تا کران بالا (upper bound) را بگیرید: اولین آیتمی که اکیداً از x بزرگ‌تر است.

def upper_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo

این دو با هم کلِ بلوکِ آیتم‌های مساوی را به شما می‌دهند؛ پس شمردنِ تکراری‌ها در یک لیست مرتب O(log n) طول می‌کشد، نه O(n):

upper_bound(a, 23) - lower_bound(a, 23)   # 2
a[lower_bound(a, 23):upper_bound(a, 23)]  # [23, 23]

نسخهٔ کلی: اولین True#

دوباره به آن دو تابع نگاه کنید. تنها چیزی که فرق می‌کند یک شرط است که مدتی False است و از یک جایی به بعد True:

index:      0      1      2      3      4     5     6     ...
a[i] >= 23: False  False  False  False  True  True  True  ...
                                        ↑ the answer

پس جست‌وجوی دودویی در واقع مرزِ یک سؤالِ بله/نه را پیدا می‌کند، به شرطی که جواب‌ها هرگز از True به False برنگردند. این ارزشِ یک تابعِ جداگانه را دارد:

def first_true(lo, hi, pred):
    """Smallest i in [lo, hi) where pred(i) is True, or hi if there is none.
    pred must be False, False, ..., True, True over that range."""
    while lo < hi:
        mid = (lo + hi) // 2
        if pred(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

lower_bound(a, x) فقط همان first_true(0, len(a), lambda i: a[i] >= x) است. اما شرط اصلاً به آرایه نیازی ندارد.

جست‌وجوی دودویی روی جواب#

ریشهٔ دومِ صحیحِ n بزرگ‌ترین r است که r * r <= n. به بیان دیگر، یکی کمتر از اولین r است که r * r > n:

def isqrt(n):
    return first_true(0, n + 1, lambda r: r * r > n) - 1

isqrt(50)          # 7
isqrt(10**12)      # 1000000, in about 40 steps

این ترفند یک خانوادهٔ کامل از مسئله‌های «کمترین مقداری که جواب می‌دهد را پیدا کن» را حل می‌کند. فرض کنید یک کامیون باید بسته‌ها را به ترتیب تحویل دهد، روزی capacity کیلوگرم بار ببرد و همه‌چیز باید ظرف days روز تحویل داده شود. کمترین ظرفیتی که کافی است چقدر است؟

def days_needed(weights, capacity):
    days, load = 1, 0
    for w in weights:
        if load + w > capacity:      # doesn't fit: start a new day
            days, load = days + 1, 0
        load += w
    return days

def min_capacity(weights, days):
    lo, hi = max(weights), sum(weights)
    return first_true(lo, hi, lambda c: days_needed(weights, c) <= days)

min_capacity([3, 2, 2, 4, 1, 4], days=3)   # 6: [3, 2] [2, 4] [1, 4]

پیدا کردنِ مستقیمِ ظرفیت سخت است، اما بررسیِ یک ظرفیت آسان است، و جواب یکنوا (monotonic) است: اگر ظرفیت ۶ کافی باشد، ۷ هم کافی است. جست‌وجوی دودویی یک بررسیِ آسان را به یک جست‌وجوی سریع تبدیل می‌کند: O(n log S) به‌جای امتحان کردنِ تک‌تکِ ظرفیت‌ها تا S = sum(weights).

چند جزئیاتِ مرزی که همه از همان الگو نتیجه می‌شوند: ظرفیت نمی‌تواند از سنگین‌ترین بسته کمتر باشد، پس lo = max(weights). hi = sum(weights) را می‌دهیم با اینکه first_true هرگز خودِ hi را امتحان نمی‌کند: اگر هیچ ظرفیتِ کوچک‌تری جواب ندهد، hi را برمی‌گرداند، که درست است، چون بردنِ همه‌چیز در یک روز همیشه شدنی است.

باگ‌هایی که باید حواستان باشد#

آن را با نسخهٔ کُند بسنجید#

جست‌وجوی دودویی نامزدِ کاملی برای تستِ مقایسه با روش brute-force است: یک پیمایشِ خطی به‌وضوح درست است، پس روی هزاران ورودیِ تصادفی، از جمله لیست‌های خالی و تکراری‌ها، با آن مقایسه کنید:

import random

for _ in range(10_000):
    a = sorted(random.randint(0, 20) for _ in range(random.randint(0, 15)))
    x = random.randint(-2, 22)
    expected = next((i for i, v in enumerate(a) if v >= x), len(a))
    assert lower_bound(a, x) == expected, (a, x)

مقدارهای کوچک (۰ تا ۲۰) تعداد زیادی تکراری و حالت مرزی می‌سازند. این نوع تست همهٔ باگ‌های جدول بالا را در کسری از ثانیه پیدا می‌کند.

جمع‌بندی#

• به‌جای «آیا x اینجاست؟» بپرسید «اولین آیتمِ ≥ x کجاست؟» (کران پایین).
• از بازهٔ نیمه‌باز [lo, hi) با while lo < hi، lo = mid + 1 و hi = mid استفاده کنید. هر مرحله بازه را کوچک‌تر می‌کند و در پایان lo جواب است.
• جست‌وجوی دودویی مرزِ هر سؤالِ بله/نهِ یکنوا را پیدا می‌کند؛ پس می‌توانید روی جواب‌ها (ظرفیت‌ها، اندازه‌ها، زمان‌ها، کامیت‌ها) جست‌وجو کنید، نه فقط روی آرایه‌ها.
• در پایتون اول سراغ bisect بروید.
• با یک نسخهٔ brute-force و ورودی‌های تصادفیِ کوچک تست کنید.