البحث الخطي مقابل البحث الثنائي – عدّ المقارنات

ماذا تعرض

يفحص البحث الخطي العناصر واحدًا تلو الآخر من البداية، لذلك يحتاج في أسوأ الحالات إلى عدد من المقارنات يساوي عدد العناصر. أما البحث الثنائي فيقارن الهدف بالعنصر الأوسط في مصفوفة مرتبة ويستبعد النصف الذي لا يمكن أن يحتويه، فلا يحتاج إلا إلى نحو log₂n + 1 مقارنة على الأكثر، أي خمس مقارنات فقط لستة عشر عنصرًا. ويبيّن عدّ المقارنات في الخوارزميتين على المصفوفة نفسها لماذا يتفوق البحث الثنائي في القوائم الطويلة، ولماذا يعتمد كليًا على أن تكون البيانات مرتبة أولًا.

طريقة الاستخدام

اضبط «الخوارزمية» على «كلتاهما (مقارنة)»، واختر «عدد العناصر»، واضغط «خطوة» لتتابع كل مقارنة: الخلية المظللة، ومؤشرات أدنى وأوسط وأعلى، وجزء المصفوفة المستبعد. انقر خلية لتغيير الهدف، أو استخدم «تشغيل» لتنفيذ كامل. جرّب هدفًا قريبًا من بداية المصفوفة، ثم ألغِ «المصفوفة مرتبة تصاعديًا» لترى لماذا لم يعد البحث الثنائي صالحًا للاستخدام.

المعاملات القابلة للتغيير

• عدد العناصر 5–20
• قيمة الهدف (0 = اختيار عشوائي من المصفوفة) 0–99
• الخوارزمية كلتاهما (مقارنة), البحث الخطي, البحث الثنائي
• المصفوفة مرتبة تصاعديًا
• سرعة التشغيل 1–5 خطوة/s

أسئلة للاستكشاف

1. ما أكبر عدد من المقارنات يحتاج إليه البحث الثنائي ليجد قيمة في مصفوفة من 16 عنصرًا؟
2. لأي قيم الهدف يحتاج البحث الخطي إلى مقارنات أقل من البحث الثنائي؟
3. لماذا لا يمكن استخدام البحث الثنائي عندما تكون المصفوفة غير مرتبة؟