الدرس 8: البحث الثنائي

لنلعب لعبة تخمين: اخترت رقمًا بين 1 و100، وفي كل تخمين أقول 'أعلى من اللازم' أو 'أقل من اللازم'. الحركة الذكية: خمّن المنتصف في كل مرة واستبعد نصف الخيارات. هذا بالضبط هو 'البحث الثنائي' — خوارزمية تجد قيمة في قائمة مرتبة، وتنصّف المرشحين في كل خطوة. النتيجة: O(log n)، سريع بشكل مذهل — حتى مليار عنص

البحث الثنائي أشبه بالبحث عن كلمة في قاموس سميك: أنت لا تقرأ صفحة صفحة من البداية. تفتح على المنتصف، وإذا كانت كلمتك تأتي لاحقًا في الأبجدية، فإنك تتخلص من النصف الأول كله دفعة واحدة. كل نظرة خاطفة تقسم ما تبقى للبحث فيه إلى النصف.

البحث الثنائي: خوارزمية بحث على مصفوفة مرتبة تفحص في كل خطوة المنتصف وتستبعد النصف الذي لا يمكن أن يحتوي على الهدف — O(log n).
الزمن اللوغاريتمي: O(log n): عدد الخطوات ينمو ببطء شديد — كل مضاعفة لـ n تضيف خطوة واحدة فقط، لأن مساحة البحث تُنصّف في كل مرة.
مساحة البحث: مجال الفهارس [low, high] الذي قد لا يزال يحتوي على الهدف؛ يقلّصه البحث الثنائي إلى النصف في كل دورة.