البحث الثنائي
يجد قيمة في مصفوفة مرتبة بالنظر إلى المنتصف واستبعاد النصف الذي لا يمكن أن تكون فيه. كل مقارنة تقسم الباقي إلى النصف.
- الأفضل Ω(1)
- المتوسط Θ(log n)
- الأسوأ O(log n)
- الذاكرة O(1)
ماذا تعني هذه المصطلحات؟
- مرتبة: بترتيب تصاعدي. يحتاج البحث الثنائي إلى ذلك؛ وعلى البيانات غير المرتبة يعطي إجابات خاطئة.
- التنصيف: كل مقارنة تستبعد نصف الباقي، النصف الذي لا يمكن أن يكون الهدف فيه.
- log₂ n: كم مرة يمكن تنصيف n حتى يبقى 1. لـ 64 قيمة الجواب 6، أي 7 مقارنات على الأكثر.
- المنتصف (mid)
- وُجد
- مستبعد
- الهدف
كل منتصف قد يختاره البحث؛ والتشغيل مسار واحد إلى الأسفل. المستويات: 5 = ⌈log₂(24 + 1)⌉، أكثر عدد من المقارنات قد يحتاجه.
نبحث عن 70 بين القيم المرتبة (n = 24): المصفوفة كلها ما زالت في اللعب.
مفتاح المسافة: تشغيل أو إيقاف مؤقت. السهمان الأيسر والأيمن: خطوة بخطوة. Home وEnd: الانتقال المباشر.
جرّب هذا: اختر هدفًا ليس في المصفوفة. سيتوقف البحث مع ذلك بعد ⌈log₂(n + 1)⌉ مقارنة على الأكثر، حين تتجاوز lo العلامة hi.
كيف يعمل
يحتفظ البحث الثنائي بعلامتين، lo وhi، حول الجزء من المصفوفة الذي قد يكون الهدف فيه. ينظر إلى القيمة في المنتصف: إن كانت الهدف انتهى؛ وإن كانت أصغر فلا يكون الهدف إلا على اليمين، فتنتقل lo إلى ما بعد المنتصف؛ وإن كانت أكبر تنتقل hi إلى ما قبله. كل خطوة تقسم الباقي إلى النصف: 64 قيمة تحتاج 7 مقارنات على الأكثر، والمليون 20 على الأكثر. حين تتجاوز lo العلامة hi لا يبقى شيء: القيمة ليست في المصفوفة.
متى يكون خيارًا جيدًا
استخدم البحث الثنائي كلما كانت البيانات مرتبة وأمكنك القفز إلى أي موضع: كلمة في قائمة مرتبة، إصدار في سجل الإصدارات، git bisect، موضع الإدراج في مصفوفة مرتبة. على البيانات غير المرتبة يعطي إجابات خاطئة، والترتيب المسبق لا يستحق إلا إذا بحثت مرات كثيرة.