تفکر الگوریتمی

جست‌وجوی دوبخشی (Bisection) در پایتون: محاسبهٔ ریشهٔ دوم

۵ دقیقه مطالعه · به‌روزرسانی ۲۲ مهر ۱۴۰۵

در روش گام‌به‌گام از صفر شروع می‌کردیم و ذره‌ذره جلو می‌رفتیم؛ برای دقت بالا، میلیون‌ها حدس لازم بود. حالا ایدهٔ هوشمندانه‌تری را می‌بینیم که همان کار را با چند ده حدس انجام می‌دهد.

ایده: هر بار نصفش کن

بازی «عدد را حدس بزن» را یادتان هست؟ یکی عددی بین ۱ تا ۱۰۰ در ذهن دارد و فقط می‌گوید «بزرگ‌تر» یا «کوچک‌تر». بهترین استراتژی چیست؟ وسط را بگویید (۵۰). با هر جواب، نیمی از اعداد حذف می‌شوند. حداکثر ۷ حدس کافی است!

همین ایده برای ریشهٔ دوم x (با فرض x ≥ 1):

• می‌دانیم جواب جایی بین 0 و x است.
• وسط بازه را به‌عنوان حدس انتخاب می‌کنیم: g = (low + high) / 2.
• اگر g ** 2 به اندازهٔ کافی به x نزدیک بود، تمام.
• اگر g ** 2 > x بود، حدس خیلی بزرگ بوده؛ جواب در نیمهٔ پایینی است: high = g.
• اگر g ** 2 < x بود، حدس خیلی کوچک بوده؛ جواب در نیمهٔ بالایی است: low = g.
• دوباره وسط بازهٔ جدید را حدس می‌زنیم.

مرحلهٔ ۱:  0 ───────────────── g ───────────────── x
                     g² > x  →  جواب سمت چپ است

مرحلهٔ ۲:  0 ──────── g' ────── g
                     g'² < x  →  جواب بین g' و g است

مرحلهٔ ۳:            g' ─ g'' ─ g

در هر مرحله، طول بازهٔ جست‌وجو نصف می‌شود. به این روش جست‌وجوی دوبخشی یا تنصیف (bisection) می‌گویند.

پیاده‌سازی

x = 25
epsilon = 0.01
num_guesses = 0
low = 0.0
high = x
ans = (high + low) / 2.0

while abs(ans ** 2 - x) >= epsilon:
    num_guesses += 1
    if ans ** 2 < x:
        low = ans
    else:
        high = ans
    ans = (high + low) / 2.0

print("num_guesses =", num_guesses)
print(ans, "is close to square root of", x)

• low و high: دو سر بازه‌ای که می‌دانیم جواب داخلش است.
• ans = (high + low) / 2: حدس همیشه وسط بازه است.
• داخل حلقه: یکی از دو سر بازه به حدس فعلی منتقل می‌شود و بازه نصف می‌شود.

ردگیری اجرا

برای x = 25:

بعد از حدود ۱۳ حدس به 5.00030… می‌رسیم که مربعش کمتر از ۰٫۰۱ با ۲۵ فاصله دارد.

برای دیدن کل مسیر، یک print داخل حلقه بگذارید:

x = 789
epsilon = 0.001
num_guesses = 0
low = 0.0
high = x
ans = (high + low) / 2.0

while abs(ans ** 2 - x) >= epsilon:
    print(f"low = {low:<12.6f} high = {high:<12.6f} ans = {ans:.6f}")
    num_guesses += 1
    if ans ** 2 < x:
        low = ans
    else:
        high = ans
    ans = (high + low) / 2.0

print("num_guesses =", num_guesses)
print(ans, "is close to square root of", x)

چقدر سریع‌تر؟

چرا؟ در روش گام‌به‌گام، تعداد حدس‌ها با طول بازه تقسیم بر گام متناسب است. در روش دوبخشی، بعد از k حدس طول بازه x / 2^k شده است؛ پس تعداد حدس‌ها با لگاریتم متناسب است. اگر دقت را هزار برابر کنید، روش گام‌به‌گام هزار برابر کندتر می‌شود و روش دوبخشی فقط حدود ۱۰ حدس بیشتر لازم دارد (چون 2^10 ≈ 1000).

💡 همین ایده پایهٔ جست‌وجوی دودویی (binary search) است، یکی از مهم‌ترین الگوریتم‌های علوم کامپیوتر: پیدا کردن یک اسم در دفترچه‌تلفن مرتب‌شدهٔ یک میلیون نفری با حداکثر ۲۰ مقایسه. git bisect هم با همین روش کامیتی را پیدا می‌کند که باگ را وارد کرده است.

محدودیت این کد

اگر 0 < x < 1 باشد (مثلاً x = 0.25)، ریشهٔ دوم (۰٫۵) بزرگ‌تر از خود x است و بیرون بازهٔ [0, x] می‌افتد. الگوریتم هرگز به آن نمی‌رسد و حلقه بی‌نهایت می‌شود.

x = 0.25
epsilon = 0.0001
low = 0.0
high = max(x, 1.0)
ans = (high + low) / 2.0
while abs(ans ** 2 - x) >= epsilon:
    if ans ** 2 < x:
        low = ans
    else:
        high = ans
    ans = (high + low) / 2.0
print(ans)

تمرین

کد بالا را طوری تغییر دهید که ریشهٔ سوم یک عدد مثبت را با روش دوبخشی حساب کند. با cube = 128 امتحان کنید و تعداد حدس‌ها را با روش گام‌به‌گام مقایسه کنید.

cube = 128
epsilon = 0.0001
num_guesses = 0
low = 0.0
high = max(cube, 1.0)
ans = (high + low) / 2.0

while abs(ans ** 3 - cube) >= epsilon:
    num_guesses += 1
    if ans ** 3 < cube:
        low = ans
    else:
        high = ans
    ans = (high + low) / 2.0

print("num_guesses =", num_guesses)
print(ans, "is close to the cube root of", cube)