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

محتوای نمونه برای ارزیابی طراحی؛ پیش از استفاده، شرایط محیط خود را بررسی کنید.

پیش‌نیازها

آرایه باید صعودی مرتب باشد. در این نسخه hi عضو بازه نیست و در آغاز برابر طول آرایه است.

راه‌حل

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

خروجی همیشه در بازه صفر تا len(a) است. اگر مقدار وجود نداشته باشد، محل درج را می‌دهد؛ برای بررسی برابری باید ابتدا کران خروجی را کنترل کنید.

نکته‌ها و خطاهای رایج

حالت آرایه خالی، مقادیر تکراری و هدف بزرگ‌تر از همه اعضا را تست کنید. ترکیب قرارداد نیمه‌باز با شرط lo <= hi از خطاهای رایج مرزی است.