البحث الثنائي
مُقدَّم| English | المعنى |
|---|---|
| sorted/ˈsɔːtɪd/ | مرتب |
| Binary search/ˈbaɪnəri sɜːtʃ/ | بحث ثنائي |
| target/ˈtɑːɡɪt/ | هدف |
| middle/ˈmɪdl/ | وسط |
| halves/hɑːvz/ | نصفين |
| comparison/kəmˈpærɪsn/ | مقارنة |
| linear search/ˈlɪnɪə sɜːtʃ/ | بحث خطي |
البحث السريع في قائمة مرتبة
- البحث الثنائي هو طريقة سريعة لإيجاد قيمة هدف في قائمة مرتبة.
- "مرتبة" تعني أن القيم مرتبة — من الأصغر إلى الأكبر، مثلاً.
- هي أسرع بكثير من التحقق من كل عنصر.
- لكن لها شرطاً واحداً صارماً.
البحث الثنائي يحتاج بيانات مرتبة. على قائمة غير مرتبة قد تقفز فوق الهدف وتخطئه. قم بالفرز أولاً دائماً — أو استخدم بحثاً مختلفاً.
يمكن استخدام البحث الثنائي فقط على بيانات:
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
على البيانات غير المرتبة قد يفتقد الهدف.
تحقق من المنتصف، ثم نصف المسافة
- الفكرة بسيطة: تحقق من العنصر الوسطي. ثم:
- إذا كان الوسطي مساوياً للهدف، لقد وجدته;
- إذا كان الهدف أصغر، ابحث فقط في النصف الأيسر;
- إذا كان الهدف أكبر، ابحث فقط في النصف الأيمن.

البحث الثنائي ينصف النطاق في كل خطوة (يجب أن تكون القائمة مُرتبة)
البحث الخطي مقابل الثنائي
الثنائي يُضعف النطاق في كل خطوة
البحث الخطي يفحص كل عنصر؛ البحث الثنائي يقسم قائمة مرتبة إلى النصف في كل مقارنة، لذا يحتاج خطوات أقل بكثير.
إذا كان الهدف أكبر من العنصر الأوسط، يبحث البحث الثنائي التالي في:
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
يجب أن يكون الهدف الأكبر في النصف الأيمن (الأعلى).
كل مقارنة في البحث الثنائي ______ الجزء المتبقي من القائمة.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
تقسيم النصف في كل خطوة هو سبب سرعته العالية.
كم عدد فحوصات البحث الثنائي المطلوبة لقائمة مرتبة بحجم 1000 عنصر؟ (2^10 = 1024)
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
لأن 2^10 = 1024 ≥ 1000، حوالي 10 تقسيمات للنصف تكفي.
لماذا هي سريعة جداً
- كل مقارنة تُنصف الجزء المتبقي من القائمة.
- بالنسبة لـ 1000 عنصر، قد تحتاج عملية البحث الخطي إلى ما يصل إلى 1000 فحص.
- البحث الثنائي يحتاج إلى ما لا يزيد عن 10 تقريباً، لأن $2^{10} = 1024$.
- كلما كانت القائمة أكبر، زادت الميزة النسبية.
يوجد البحث الثنائي 14 في [2,5,8,11,14,17,20] بعد كم مقارنة؟
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
الوسط 11 → اليمين؛ الوسط 17 → اليسار؛ الوسط 14 → وجد: 3 مقاربات.
على قائمة مرتبة كبيرة، تحتاج عملية البحث الخطي إلى مقارنات أقل من عملية البحث الثنائي.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
خطأ. البحث الثنائي يقسم القائمة إلى النصف في كل خطوة، لذا فهو يتطلب مقارنة أقل بكثير من فحص كل عنصر على حدة.
مقابل البحث الخطي
- يقوم البحث الخطي بفحص كل عنصر على حدة.
- يتفوق البحث الثنائي عليه في القوائم الكبيرة المرتبة عن طريق تنصف القائمة في كل خطوة.
ابحث في [2, 5, 8, 11, 14, 17, 20] عن الرقم 14. العنصر الأوسط هو 11؛ بما أن 14 > 11 → ابحث في النصف الأيمن [14, 17, 20]. العنصر الأوسط هو 17؛ بما أن 14 < 17 → ابحث في [14]. العنصر الأوسط هو 14 — تم العثور عليه بعد 3 مقارنات فقط. كان البحث الخطي سيستغرق 5.
البحث الثنائي يعثر على هدف في قائمة مرتبة بفحص العنصر الأوسط والاحتفاظ بالنصف الذي قد يحتويه فقط. كل مقارنة تُنصف النطاق، لذا فإن 1000 عنصر تحتاج ~10 فحوصات — وهو عدد أقل بكثير من 1000 فحص التي يتطلبها البحث الخطي. يعمل فقط على البيانات المرتبة.