جستجوی دودویی روی پاسخ

جستجوی دودویی روی پاسخ: وقتی به‌جای آرایه، روی «مقدار جواب» دودویی می‌کنیم — کمینه/بیشینه‌ای که شرط را برقرار می‌کند

ایده شگفت‌انگیز

جستجوی دودویی فقط برای آرایه مرتب نیست! اگر بتوانیم بگوییم «جواب مسئله در بازه [کمینه، بیشینه] است» و «برای مقدار x، بتوانیم بررسی کنیم آیا جواب ≤ x است یا نه» — روی خود جواب دودویی می‌کنیم!

شرط‌های الگو

  1. پاسخ، یک عدد در بازه مشخص است (سرعت، اندازه، روز...)
  2. تابع بررسی feasible(x) وجود دارد: «آیا با مقدار x می‌شود؟»
  3. تابع feasible تک‌ناهدی است: اگر x جواب باشد، x+1 هم هست (یا برعکس)

تک‌ناهدی یعنی جواب‌ها یک «مرز» دارند — و دودویی دقیقاً مرز را پیدا می‌کند!

الگوی کد

low, high = کمینه_ممکن, بیشینه_ممکن
while low < high:
    mid = (low + high) // 2
    if feasible(mid):
        high = mid      # جواب ≤ mid؛ کوچکتر برو
    else:
        low = mid + 1   # جواب > mid
return low   # کمینه مقدار ممکن

مسائل کلاسیک

مسئلهدودویی روی چی؟feasible؟
کاپیتان شکاری (Koko eating bananas)سرعت خوردنبا این سرعت در مهلت تمام می‌شود؟
کمینه بیشینه فاصله توپ‌هاحداقل فاصلهبا این فاصله جا می‌شوند؟
تقسیم آرایه به k زیرآرایهحداکثر جمع زیرآرایهبا این سقف، k بخش کافی است؟
روز n گل رزده می‌شودروزتا این روز همه رزده‌اند؟
کمینه ظرفیت کشتی در D روزظرفیتبا این ظرفیت در D روز تمام می‌شود؟

مثال: تقسیم آرایه

آرایه [7,2,5,10,8] را به k=2 بخش تقسیم کن که «بیشترین جمع بخش» کمینه شود:

نکته تشخیص: عبارت‌های «کمینه بیشینه»، «بیشینه کمینه»، «کوچکترین مقداری که می‌توان...» = پرچم دودویی روی پاسخ! این الگو در مصاحبه‌های سطح متوسط-پیشرفته محبوب است.

جمع‌بندی

این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.

ابزارهای مرتبط