إصلاح عقود حدود البحث الثنائي

افهم الأسباب المحتملة

• اختلطت صيغ المجالات المغلقة ونصف المفتوحة، أو لم يُزل أحد الفرعين مرشحا اختُبر وثبت استبعاده.
• تعيد الواجهة موضع إدراج، لكن المستدعين يفسرون كل موضع معاد على أنه مطابقة مساواة ناجحة. وربما لم يعد المصدر مرتبا بعد التهيئة المسبقة.

سم نوع النتيجة والتسلسل المقبول أولا

قرّر هل تَعِد الدالة بإيجاد أي ظهور مطابق وإرجاع موضعه، أم بأول موضع لقيمة مساوية، أم بموضع إدراج يمثل الحد الأدنى. تختلف هذه العقود عند وجود تكرار أو غياب القيمة. سجّل مفتاح المقارنة، وأكد أن التسلسل مرتب وفقا لتلك العلاقة نفسها بالضبط. لا تصلح حساب الحلقة مع تجاهل عينة غير مرتبة، أو مفتاح متغير، أو تعديل أثناء البحث. استخدم تسلسلا مصطنعا صغيرا، واحفظ الهدف الذي يسبب الفشل. ينبغي أن تتبع الإجابة المتوقعة العقد، وليس ناتج التنفيذ المعيب الحالي.

ارسم المناطق المعروفة والمجهولة

في بحث الحد الأدنى اختر [lo,hi) منطقة مجهولة، واجعل جميع القيم السابقة لها أصغر من target، وجميع القيم عند hi أو بعده لا تقل عنه. إذا كانت قيمة المنتصف أصغر من الهدف فهو مستبعد يقينا، فيصبح lo=mid+1. وإلا فقد يظل المنتصف هو الإجابة، فيصبح hi=mid. قبل كل تكرار اكتب العرض hi-lo، وتحقّق من تناقصه حصرا بعد أي من الفرعين. يستخدم المجال المغلق ثابتا وشرط انتهاء مختلفين؛ وقد ينشئ اقتباس أحد تحديثاته دون برهانه حالة عنصرين لا تنتهي.

سجّل تقدم البحث دون تغيير عقد النتيجة

يسجل البرنامج حدود المجالات فقط، ويؤكد التقدم الصارم. يكشف أثره الثابت المختار مع إبقاء الخوارزمية مستقلة عن بيانات التطبيق الفعلية. للهدف 3، تبدأ كتلة المكررات عند الموضع 1. ويمكن أن تساوي الإجابة النهائية len(values)، ولذلك يجب أن يظل المستدعي يفحص الحدود والمساواة قبل إعلان العضوية. أبق فحص العضوية خارج عقد الحد الأدنى، بدلا من إرجاع فهرس مطابقة مختلق. التأكيد أداة تشخيصية مساعدة؛ وتشرح حجتا التقسيم وتقلص العرض لماذا ينبغي أن يصح لكل تكرار مقبول.

def traced_lower_bound(values, target):
    lo, hi = 0, len(values)
    trace = []
    while lo < hi:
        trace.append((lo, hi))
        width = hi - lo
        mid = lo + width // 2
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
        assert hi - lo < width
    return lo, trace

print(traced_lower_bound([1, 3, 3, 8], 3))
position, _ = traced_lower_bound([1, 3, 3, 8], 9)
print(position)

(1, [(0, 4), (0, 2), (0, 1)])
4

تحقّق من خصائص التقسيم بدلا من الاكتفاء بإجابة محظوظة

عد مصفوفات صغيرة مرتبة ذات قيم متكررة، وقارن بالمرجع bisect_left أو بمرجع خطي بسيط. لكل p معاد، افحص أن كل قيمة قبله أصغر من الهدف، وأن كل قيمة ابتداء منه لا تقل عن الهدف. أدرج المدخل الفارغ والمنفرد، والقيم المتساوية كلها، وهدفا أدنى من جميع القيم، وفجوة بين قيم، وهدفا أعلى من جميع القيم. اختبر فرع العضوية لدى المستدعي وأي سياسة موعودة للتكرار بصورة منفصلة. لا تخف العيب بحد تكرارات اعتباطي يعيد منتصفا غير مثبت عندما يصل التنفيذ إلى ذلك الحد.

امنع تكرار المشكلة

• وثّق اصطلاح مجال واحدا ونوع نتيجة واحدا لكل دالة. اجعل مسؤولية حفظ الترتيب وسلوك التكرار وتحويل الحد إلى نتيجة عضوية أمورا صريحة، واحتفظ بعينة التراجع المصغرة التي تضم مرشحين.