البحث الثنائي
البحث الثنائي هو طريقتك في البحث عن كلمة في القاموس: تفتحه من المنتصف، وترى هل الكلمة قبل الصفحة أم بعدها، ثم تكرر ذلك مع ذلك النصف. وفي قائمة مرتبة يجد أي قيمة بين مليون قيمة في 20 مقارنة على الأكثر.
الفكرة
في قائمة مرتبة، تخبرك مقارنة واحدة بأكثر من مجرد العثور على القيمة المطلوبة أو عدمه: تخبرك في أي جانب توجد. قارن القيمة المطلوبة بالقيمة في المنتصف. إذا تساوتا فقد انتهيت. وإذا كانت القيمة الوسطى أصغر، فكل ما قبلها أصغر أيضًا، لذا لا يمكن أن تكون القيمة المطلوبة إلا بعدها. وإذا كانت أكبر، فلا يمكن أن تكون إلا قبلها. احتفظ بذلك النصف فقط وكرر.
مثال
ابحث عن 23 في 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. القيمة الوسطى 16، وهي أصغر، فلا يبقى إلا من 23 إلى 91. والقيمة الوسطى لهذه 56، وهي أكبر، فلا يبقى إلا 23 و38. والقيمة الوسطى لهما 23: وُجدت في الموضع 6 بعد 3 مقارنات، بينما يحتاج البحث الخطي إلى 6. والبحث في القائمة نفسها عن 40 يقارن 16 و56 و23 و38، ثم لا يبقى شيء: 4 مقارنات لمعرفة أن 40 غير موجودة، مقابل 10 للبحث الخطي.
التنصيف يتراكم بسرعة
بعد مقارنة واحدة يبقى نصف القائمة على الأكثر، وبعد اثنتين الربع، وبعد k نحو n/2ᵏ على الأكثر. يتوقف البحث عندما لا يبقى شيء، لذا يحتاج إلى ⌊log₂ n⌋ + 1 مقارنة على الأكثر: 6 لـ 40 قيمة، و10 لـ 1000، و20 لمليون، و30 لمليار. ومضاعفة القائمة تضيف مقارنة واحدة فقط. ويُكتب ذلك O(log n).
سهل الوصف، صعب الإتقان
وصف John Mauchly البحث الثنائي عام 1946، لكن بحسب Donald Knuth لم تُنشر أول نسخة تعمل مع أي طول للقائمة حتى عام 1962. ولاحقًا وجد Jon Bentley أن نحو واحد فقط من كل عشرة مبرمجين محترفين كتبه بشكل صحيح: فشروط التوقف وزيادة واحد أو نقصانه عند تقسيم النصفين سهلة الخطأ. وفي عام 2006 بيّن Joshua Bloch أن الطريقة الشائعة لإيجاد المنتصف، (low + high) / 2، قد تتجاوز السعة في القوائم الطويلة جدًا، وهو خطأ بقي في مكتبة Java سنوات. وكتابة low + (high − low) / 2، كما يفعل التطبيق، تتجنبه.
الصيغ والاستخدامات
مع القيم المكررة يجد البحث الثنائي إحدى القيم المطابقة؛ والنسخ التي تواصل نحو البداية أو النهاية تجد أول تطابق أو آخره، أو الموضع الذي تُدرج فيه قيمة غير موجودة. وفكرة التنصيف نفسها تجد جذر معادلة (طريقة التنصيف)، والنسخة التي ظهر فيها خطأ لأول مرة (git bisect)، وحل كثير من ألغاز التحسين. وتخزّن أشجار البحث الثنائية البيانات بحيث يتبع كل بحث مسار التنصيف نفسه.
جرّبه بنفسك
افتح التطبيق، واختر قيمة في «ابحث عن»، واضغط خطوة. الجزء المظلل هو حيث لا تزال القيمة المطلوبة ممكنة؛ تُبرز القيمة الوسطى، ويبهت النصف المستبعد. وتعرض المربعات عدد القيم التي لا تزال ممكنة وعدد المقارنات التي يحتاجها البحث الخطي للقيمة نفسها. ابحث عن قيمة غير موجودة، أو استخدم 40 عمودًا، لترى الفرق يكبر.
الأسئلة المتداولة
ما التعقيد الزمني للبحث الثنائي؟
O(log n): على الأكثر ⌊log₂ n⌋ + 1 مقارنة لـ n قيمة. أفضل حالة مقارنة واحدة، عندما تكون القيمة المطلوبة في المنتصف. والنسخة التكرارية تحتاج إلى ذاكرة إضافية O(1).
ما الفرق بين البحث الثنائي والبحث الخطي؟
يفحص البحث الخطي كل قيمة بالدور ويعمل على أي قائمة، لكنه قد يحتاج إلى n مقارنة. أما البحث الثنائي فلا يعمل إلا على قائمة مرتبة، لكنه يستبعد نصف المتبقي مع كل مقارنة، لذا يحتاج إلى نحو log₂ n.
هل يستحق ترتيب قائمة لمجرد استخدام البحث الثنائي؟
فقط إذا كنت ستبحث فيها مرات كثيرة. يستغرق الترتيب نحو n log n خطوة، أكثر من بحث خطي واحد. وبعد ترتيب القائمة يصبح كل بحث بعده رخيصًا جدًا.
هل يعمل البحث الثنائي على أشياء غير القوائم؟
نعم، على أي شيء يخبرك فيه اختبار في أي جانب من الإجابة أنت: نطاق من الأرقام، أو إصدارات برنامج، أو التخمينات في لعبة «أكبر أم أصغر».
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب البحث الثنائي