البحث الثنائي الكلاسيكي دون أخطاء

يعثر البحث الثنائي على قيمة في قائمة مرتبة بتقسيم النطاق إلى نصفين في كل خطوة. وبذلك يتحول المسح البطيء O(n) إلى بحث سريع بتعقيد O(log n).

لا يعمل البحث الثنائي إلا على بيانات مرتبة. إذا كانت القائمة غير مرتبة، فافرزها أولًا، وإلا كانت النتيجة بلا معنى وخاطئة.

ابدأ بمؤشرين: low عند الفهرس 0 وhigh عند الفهرس الأخير. وتبقى القيمة المستهدفة، إن وُجدت، بينهما دائمًا.

احسب mid على صورة low + (high - low) // 2. لا يمثل تجاوز السعة مشكلة في Python، لكن هذه الصيغة عادة آمنة في كل مكان.

قارن a[mid] بالقيمة المستهدفة. إما أن تكون قد عثرت عليها، أو أن تكون أصغر من المطلوب، أو أكبر منه. وتقلّص كل حالة النطاق بطريقة مختلفة.

إذا كانت a[mid] أصغر من القيمة المستهدفة، فلا بد أن تكون الإجابة إلى اليمين. حرّك low إلى mid + 1 وتخلّص من النصف الأيسر.

إذا كانت a[mid] أكبر من القيمة المستهدفة، فابحث في النصف الأيسر. حرّك high إلى mid - 1 حتى لا تعيد فحص mid.

تابع ما دام low أصغر من high أو مساويًا له. عندما يتجاوز أحدهما الآخر، يصبح النطاق فارغًا ولا تكون القيمة المستهدفة موجودة.

إذا انتهت الحلقة من دون تطابق، فالقيمة غير موجودة. أعد -1 وفقًا للعرف، حتى يتمكن المستدعي من التمييز بين النجاح والفشل.

الخطأ الشائع هو نسيان +1 أو -1 عند تحريك المؤشر. وإذا أغفلته، فستُعاد مقارنة mid إلى الأبد، ما يؤدي إلى حلقة لا نهائية.

لاختبار عضوية بسيط، توفّر وحدة bisect في Python بحثًا خاليًا من الأخطاء. اكتب الحلقة يدويًا فقط عندما تحتاج إلى منطق مخصص.

فكّر في العامل الذي يُبقي الحلقة منضبطة.

يمكنك الآن ضبط low وhigh، وحساب mid بأمان، وتقليص الجانب الصحيح، وتجنب فخ الانحراف بمقدار واحد. أصبح البحث اللوغاريتمي في متناولك. 🎯